Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
给定一个字符串s，找出其最大回文子串，s最大长度可以估算为1000.

方法一 ：暴力，O(n^3) 第一个循环决定字符串位数、第二个循环遍历从头到尾该位数的字符串、第三个循环判断其字符串是不是回文子串

方法二：O(n^2) 遍历每一个节点，再用左右找最大回文字串。注意偶数字符串aa与基数字符串aba两种情况的区分。空间复杂度O(1)

    def longestPalindrome(self, s):
        if len(s) < 2:
            return s
        start = maxlen = 0
        for i in range(1, len(s)):    
            start,maxlen = self.Palindrome(s, i-1, i+1, maxlen, start)
            start,maxlen = self.Palindrome(s, i-1, i, maxlen, start)
        return s[start:start + maxlen]
    
    def Palindrome(self, s, left, right, maxlen, start):
        while left >= 0 and right < len(s) and s[right] == s[left]:
            left -= 1
            right += 1
        if right - left - 1 > maxlen:
            maxlen = right - left - 1
            start= left + 1
        return start, maxlen

方法三：DP拆分状态，若j到i之前的字符串为回文数，那么j+1到i-1之间的字符串必定为回文字符串，把dp[i][j]定义为从i到j之间的字符串是否为回文字符串，则时间复杂度也可以减少到O(n^{2)，不过空间复杂度也变成了O(n}2)

    def longestPalindrome(self, s):
        if len(s) < 2:
            return s
        maxLen = 0
        res = ''
        dp = [ [False]*len(s) for _ in range(len(s))]
        for i in range(len(s)):
            for j in range(i+1):
                if (s[i] == s[j]) and (i-j<=2 or dp[i-1][j+1]):
                    dp[i][j] = True
                    if i-j+1 > maxLen:
                        maxLen = i-j+1
                        res = s[j:i+1]
        return res

方法四：Manacher's Algorithm马拉车算法，有个博客讲得非常好，博客地址。
Manacher's Algorithm解决了方法二存在的两个问题

1. 回文长度奇偶性问题，通过再所有字符加入“#”后，每个字符回文长度为n - 1解决
2. 重复访问问题，在已经确定是回文数的情况下，回文数内部的子回文数重复计算可以快速获取，具体可以看博客地址，写的比较详细。

       def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        t = s
        s = "#" + "#".join(s) + "#"
        maxright, maxlen, i, pos = 0, 0, 0, 0
        RL = [0] * len(s)
        res = ""
        for i in range(len(s)):
            #最关键的一个判断，缩短了大回文中小回文的判断
            if i < maxright:
                RL[i] = min(RL[2*pos-i], maxright - i)
            else:
                RL[i] = 1
            #更新 i的最大回文长度
            while i + RL[i] < len(s) and i - RL[i] >= 0 and s[i+RL[i]] == s[i-RL[i]]:
                RL[i] += 1
            #更新 maxright and pos
            if maxright < i + RL[i] - 1:
                maxright = i + RL[i] - 1
                pos = i
            #记录结果
            if maxlen < RL[i]:
                maxlen = RL[i]
                res = t[(i + 1 - maxlen)//2: (i - 1 + maxlen)//2]
        return res

空间复杂度：插入分隔符形成新串，占用了线性的空间大小；RL数组也占用线性大小的空间，因此空间复杂度是线性的。
时间复杂度：尽管代码里面有两层循环，通过amortized analysis我们可以得出，Manacher的时间复杂度是线性的。由于内层的循环只对尚未匹配的部分进行，因此对于每一个字符而言，只会进行一次，因此时间复杂度是O(n)。