Let an integer n be given. Write the integers from 1 to n in binary notation successively from left to right. In the resulting string consisting of zeros and ones, choose a palindrome substring of maximal length. It is required to find the length of this substring. For example, if n=5, we can get a string which is 1 10 11 100 101. And we can get the longest substring that is palindromic: 11011 or 01110. So the answer to the question is 5. The n can be very big. Are there any good algorithm to solve this problem? Thanks in advance!
You could use a regular palindrome substring search algorithm, such as as Manache's Algorithm. It would still be optimal, i guess, even considering that your string is binary. Take a look at that algorithm.