5. Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:


Note: “aba” is also a valid answer.
Example:


I have misunderstood the meaning of the word palindrome , i thought it was the meaning of repeat,finally i know that it was the meaning of a string which is the same when you look from left to right and from right to left.
According to that , we know it has two situation,one the length is odd , another is even .
Approach 1 :


Analysis
This method divided the problem into two situation.First we loop the every char of the String,each char call the extendPalindrome method .The extendPalindrome method is used to find the char of corresponding position is the same or not . if so we move the index of the left char to left one ,and the right char to right one,and then repeat this procedure.
Time complexity ： O(n^2) 。n is the length of the string.
Space complexity ： O(n) .
Approach 2 :


Analysis
This method is when then index move to right , we used the char of this index as the end of the substring which length is current length +1 or current length +2, and see if is the Palindrome string .
Time complexity ： O(n^2) 。n is the length of the string.
Space complexity ： O(n) .
Approach 3 (Manacher’s Algorithm)


Analysis
In this question,the Palindrome has two situation, one is even Palindrome , another is odd Palindrome. In order to combine them into one situation, we can add a special char like ‘#’ between every two char of the string which is neaby ,and the begining and the ending of the string . like “#a#b#b#c#a#”. Now we have combine the two situation into together.
In the String s ,we use rad[i] to represent the Palindrome radius of index i , we can get s[irad[i],i1] = s[i+1,i+rad[i]] easily , once we get the all the rad of the String , we get the all the Palindrome which is even length .
when we get the value of rad[1..i1],and get the rad value of the char i is at least j through compare char which is symmetry.Now we suppose that we have a index k , it start from 1 to rad[i],we can use it to get the rad valule of the [i+1,i+rad[i]].
According to the acept of the Palindrome , we know the part of the black is a Palindrome, two parts of the red have the same length.
Because we have calculate the value of rad[ik],so we can use it . There are three situations:
(1)rad[i]k < rad[ik]
As the picture , rad[ik]’s range is blackish green line . Because of the black line is Palindrome,and a part of blackish green line is out of the black line,so rad[i+k] is at least rad[i]k (the orange line).Is there have any possible that rad[i+k] is larger than rad[i]k? it’s impossible ,according to the acept of the Palindrome ,we know that if the part out of the orange line is the Palindrome , than the black line can expand outward. Is different from the suppose we have done . so rad[i+k] = rad[i]k。
（2）rad[i]k > rad[ik]
As the picture , rad[ik]’s range is the blackish green line . Because the black line is Palindrome and the blackish green line is in the black line , according to the acept of the Palindrome ,we can get that rad[i+k] = rad[ik] easily.
According to the situation we have talk , we can get that when rad[i]k != rad[ik] ,rad[i+k] = min(rad[i]k,rad[ik])。
（3）rad[i]k = rad[ik]
As the picture , after compare to the first situation , we can find that because the blackish line is in the black line , so even the orange line is equals , it can’t cause a contradiction like situation 1 ,so the orange line can be equals . But , according to the message we know , we have not idear how long is the orange line , so we put the i to the i+k position , j=rad[ik](because it’s rad is at least rad[ik]), wait to next loop to calculate it can expand out or not .
Time complexity ： O(n) 。it looks like the program is use the nesting loop ,but actualy it only calculate the i which haven’t calculated.
Space complexity ： O(n) .
If you have any suggestions to make the logic and implementation more better , or you have some advice on my description. Please let me know!Thanks!
About Me
My blog leonchen1024.com
My Github https://github.com/LeonChen1024
My twitter https://twitter.com/LChen1024?lang=en