This problem can be interpreted as:

A reduced problem: given string S and constant length L, return the
palindrome (if exist).
Now I only get O(n^2) solution for this reduced problem, but I believe that there are O(n) solution to this sub problem, since there is already O(n) solution to the original problem O(n) solution 
A BiSearch process to find the longest length for the reduced problem. Note that if there exists a palindrome of length N (N>=2), there must be palindrome of length N2. This makes me think of
BinarySearch method. For example, Given string S length of 10. Then the possible palindrome length falls in two search zones: odd = [1,3,5,7,9] even = [2,4,6,8,10] Then we perform bisearch in these two zone separately.
Because the complexity of bisearch is O(log(n)), so the overall complexity = O(n*log(n))