题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

解答

很容易想到使用暴力法来解决，检查字符串s所有的子串，从所有的回文子串中，找出最长的回文子串。方法很简单，代码就不写了，构造所有的子串时间复杂度是O(n^2)，检查一个子串是否是回文串的时间复杂度是O(n)，暴力法整个算法时间复杂度是O(n^3)。空间复杂度是O(1)

但使用中心扩散法可以优化时间复杂度。

具体思路是：我们遍历字符串中的每一个字符，将当前字符或者当前字符和下个字符的中心位置作为子串的中心位置，然后检查当前子串是否是回文字符串。如果是，那就继续向左和向右扩展，直到左边的字符不等于右边的字符，那么之前的子串就是，以当前字符串为中心的最长回文串。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2:
            return s

        max_len = 0
        begin = 0
        for i in range(0, len(s) - 1):
            # 求以当前字符为中心的最长回文子串
            odd_begin, odd_len = self.expand_around_center(s, i, i)
            # 求以当前字符和下一个字符中间位置为中心的最长回文子串
            even_begin, even_len = self.expand_around_center(s, i, i+1)
            cur_max = max(odd_len, even_len)
            if cur_max > max_len:
                begin = odd_begin if odd_len >= even_len else even_begin
                max_len = cur_max
            
        return s[begin : begin + max_len]
        

    def expand_around_center(self, s:str, i:int, j:int) -> (int, int):
        # 返回最长回文串的起始索引和长度
        s_len = len(s)
        while i >= 0 and j < s_len:
            if s[i] == s[j]:
                i -= 1
                j += 1
            else:
                break
        return i + 1, j - i - 1

时间复杂度是O(n^2)，空间复杂度是O(1)。