I cannot think of any that has a complexity less than O(n*n).
one of the ways would be :
1. Take the string (s1) and its direct reversal (s2)
2. Slide s2 over s1 per character and count the number of similar characters starting from s2′s last character
Hence, first:
———————— ABCDAMNMADGHJ
JHGDAMNMADCBA Count =1
Then,
————————ABCDAMNMADGHJ
–JHGDAMNMADCBA Count=0
.
.
.
————————ABCDAMNMADGHJ
————————JHGDAMNMADCBA Count=7
.
.
.
————————ABCDAMNMADGHJ Count= 0 We can exit at this point
—————————————JHGDAMNMADCBA
.
.
and last
————————ABCDAMNMADGHJ
————————————————-JHGDAMNMADCBA Count=1
We can slightly optimise this by remembering the biggest palindrome count (maxCount) and stopping at the point when maxCount > numbers of characters left to compare.
This is pretty naive way!!!!
Better Way - Use Dynamic Programming
1. Reverse the string
2. Find the LCS between the original string and reversed string.