给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1：

输入： s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2：

输入： s = “cbbd”
输出：“bb”

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 预处理字符串：在每个字符之间加上分隔符 '#'
        # 这样能把奇数和偶数长度的回文统一处理
        # 例如 "abba" -> "#a#b#b#a#"
        t = '#' + '#'.join(s) + '#'
        n = len(t)
        p = [0] * n  # p[i] 表示以 i 为中心的最长回文半径
        c = r = 0    # c: 当前回文中心；r: 当前回文的最右边界
        max_len = 0
        center = 0

        # 主循环：遍历每个字符
        for i in range(n):
            mirror = 2 * c - i  # i 关于中心 c 的对称点

            # 如果 i 在当前回文的右边界内，则可用镜像的结果减少比较次数
            if i < r:
                p[i] = min(r - i, p[mirror])

            # 尝试扩展回文
            while i - p[i] - 1 >= 0 and i + p[i] + 1 < n and t[i - p[i] - 1] == t[i + p[i] + 1]:
                p[i] += 1

            # 若超出右边界，则更新中心与右边界
            if i + p[i] > r:
                c, r = i, i + p[i]

            # 记录最大回文长度和中心
            if p[i] > max_len:
                max_len, center = p[i], i

        # 计算原字符串中的起止位置
        start = (center - max_len) // 2
        return s[start:start + max_len]