My idea is to reverse the operations of adding characters and doubling a string. I have an iterative algorithm in O(n * log(n)). At each iteration, I count dp - the length of the maximum substring ending with index i, obtained by the doubling operation. Then I look for the maximum among the maximum substrings and truncate the current string to leave this substring. But this is a greedy solution. Is it possible to come up with a counterexample to it?