# 5. Longest Palindromic Substring
[題目](https://leetcode.com/problems/longest-palindromic-substring/)
在leetcode 用英文解釋過了，所以這邊有點懶得打，需要中文解釋在留言跟我說
I have seen a [easy-understanding video](https://www.youtube.com/watch?v=nbTSfrEfo6M)，so I can make it.
Manacher's algorithm has an important point to break a hurting point.
The hurting point is we have to expand every center what make our time complexity O(N^2)
How can we break the point? We use the palindromic we count before.
s=abababa
P=1357???
In the range , as you can see ??? should be 531.
Can we replace ??? into 351 or not, just like the P in the mirror place?
NONONO
if there is other character in the end, like this:
s=abababa|b
P=1357??? ?
take the last **'a'** as a center，a's ? should be 3, not 1. So here we know **if you are in the right boundary only thing we can know is >=P[mirror place]**
SO, now we can start to code

If you want see detial with an example or wornding I didn't tell the detial. Watch the video.
And if there is anythong wrong, tell me and I will fix it.

#problem:https://leetcode.com/problems/longest-palindromic-substring/
class Solution:
    def longestPalindrome(self, s: str) -> str:
        modified='@#'+'#'.join(list(s))+'#$'   
		#we have to seperate string  with #, and plus different character，since sometimes we have string like 'baab'
        P=[0]*len(modified)#[0,0,0......,0]
        max_P,longPalindromic=0,0
        C,R=1,1
        for i in range(1,len(modified)-2):
            mirr=C-(i-C)#locate mirror place for current center.
            if i<R:
                P[i]=min(R-i,P[mirr])#As I metion above, if it's in range P[i]>=P[mirror place]
            while modified[i+1+P[i]]==modified[i-1-P[i]]:#since P[i]>=P[mirror place] we only have to check the character out of P[i]
                P[i]+=1
            if i+P[i]>R:#If outside the range we should find our new center
                C=i
                R=C+P[C]
            if P[i]>=max_P:#record Longest Palindromic Substring
                max_P=P[i]
                longPalindromic=i
        ans=''.join(modified[longPalindromic-max_P:longPalindromic+max_P].split('#'))
        return ans

###### tags: `LeetcodeMedium` `python`