class Solution:
    def longestPalindrome(self, s: str) -> str:
        n=len(s)
        def helper(i,j):
            while i>=0 and j<n and s[i]==s[j]:
                i-=1
                j+=1
            return i+1,j-1 #回复到原本状态
        st,e=0,0
        for i in range(0,n):
            a,b=helper(i,i)
            if b-a>e-st:
                st,e=a,b
            c,d=helper(i,i+1)
            if d-c>e-st:
                st,e=c,d
        return s[st:e+1]

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n=len(s)
        dp=[[0 for _ in range(n)] for _ in range(n)]
        ans=1
        idx=0
        for i in range(n):
            dp[i][i]=1 #本身就是回文串
            if i+1<n and s[i]==s[i+1]:
                dp[i][i+1]=1  #两个最基本的连续
                if ans<2:
                    ans=2
                    idx=i
        
        for k in range(3,n+1):# 从3~n进行遍历 如果这个字符串整个都是 回文串的话
            for i in range(n):
                j=k+i-1
                if j>=n:break
                if s[i]==s[j] and dp[i+1][j-1]==1:
                    dp[i][j]=1
                    if ans<k:
                        ans=k
                        idx=i
        return s[idx:idx+ans]

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # manacher马拉车    
        ls='#'+'#'.join(list(s))+'#'
        n=len(ls)
        p=[1]*n #改进一下 -->初始化为1 即可
        r,c=0,0
        ans,idx=0,0
        for i in range(1,n):
            if i<r:
                p[i]=min(p[2*c-i],c+p[c]-i)
            # 暴力中心扩散
            while i+p[i]<n and i-p[i]>=0 and ls[i+p[i]]==ls[i-p[i]]:p[i]+=1

            # 更新回文中心即可
            if i+p[i]>r:
                r=i+p[i]
                c=i
            # 用作数据统计分析
            if p[i]>ans:
                ans,idx=p[i],i

        ans-=1
        st=(idx-ans)//2
        return s[st:st+ans]