LC5　最长回文子串¶

中等通过率 41.1%python3核心代码模式多维动态规划样例通过牛客 AC双指针字符串动态规划Manacher 算法

牛客原题　源码

讲解章节：回文

一句话

逐个枚举回文中心向两边同步外扩，扩不动时记下这一段的起点与长度。

解题思路¶

这题考什么¶

回文的判定天然是递归的：s 的第 i 到第 j 个字符构成回文，当且仅当两端字符相同、且去掉两端后的里层也是回文。写成区间动态规划就是：

状态定义：f[i][j] 表示子串 s[i..j]（含两端）是否为回文。转移方程：

f[i][j] = (s[i] == s[j]) 且 f[i+1][j-1]

初值：长度为 1 的区间恒为回文；长度为 2 时里层是空区间，按回文处理，于是 f[i][i+1] 就等于 s[i] == s[i+1]。因为要用到「行号更大」的 f[i+1][...]，i 必须倒序填表，正序时它还没算出来。区间 DP 的一般形式见区间 DP。

把这条递推反过来读，就得到本文件采用的中心扩张： f[i][j] 依赖 f[i+1][j-1]，同一条依赖链上所有区间的中心是同一个。与其填满整张二维表，不如直接固定中心、向两侧同步外扩：只要两端字符相等就继续扩，一旦不等或越界就停——停下时得到的正是以该中心为轴的最长回文。这样时间同为 O(n 的平方)，空间却从 O(n 的平方) 降到 O(1)。

中心有两类，必须都枚举：

奇数长度的回文，轴是某个字符本身，如 "aba" 的 'b'，从 (i-1, i+1) 起扩；
偶数长度的回文，轴落在两个字符之间的缝里，如 "bb" 的中缝，从 (i, i+1) 起扩。

n 个字符加 n-1 条缝，共 2n-1 个中心。只做奇数中心时 "cbbd" 会返回 "c"，只做偶数中心时 "aba" 会返回空。

还有 O(n) 的 Manacher 算法，靠已经求出的回文半径去推后面的位置。本题 n <= 1000，中心扩张的 5e5 次比较绰绰有余，不必上这套更难写的方法。

数据规模与复杂度¶

1 <= s.length <= 1000，仅由数字和英文字母组成（因此不必考虑大小写等价或空白）。中心数 2n-1 约 2000，每个中心至多向外扩 n/2 步，最坏是全同字符的 "aaa...a"（每个中心都要扩到边界），约 n 的平方 / 2 = 5e5 次字符比较，本机实测长度 1000 的全同字符串约 0.04 秒。空间 O(1)，只有四个整数。

与之对照，枚举所有子串再逐个验证是 O(n 的三次方) = 1e9，n = 1000 时不可行；区间 DP 是 O(n 的平方) 时间加 O(n 的平方) 空间，1e6 个布尔格子也能过，但中心扩张在同样的时间里省掉了整张表。

坑在哪¶

要返回子串本身，不是长度。所以必须同时记录起点与长度，只维护一个最大长度是还原不出答案的。返回时用 s[start:start+length] 切片，右端点是开区间，写成 s[start:start+length+1] 会多带一个字符。
while 退出时 left 与 right 已经越过了回文的两端（要么下标越界，要么两个字符不相等），真正的回文是开区间 (left, right)，长度是 right - left - 1，起点是 left + 1。直接写 right - left 会凭空多算 2，这是本题最常见的下标错误。
更新条件必须是严格大于。写成大于等于时，同样长度的后来者会顶掉先到者： "babad" 的奇数中心扫到下标 2 时会得到同样长 3 的 "aba"，于是返回 "aba" 而不是样例期望的 "bab"。本地样例走严格比对，会判错。
两种中心的起手位置不同：奇数中心是 (i-1, i+1)，一开始就跳过了轴字符本身（单个字符必然回文，不必比较）；偶数中心是 (i, i+1)，第一次比较的就是两个相邻字符，它们不等时循环立刻结束，得到长度 0，不会污染答案。
起手的 length 取 1 而不是 0。题面保证串非空，答案至少是一个字符；取 0 的话若所有中心都扩不动（如 "abcd"），返回的会是空串而不是 "a"。
边界检查 left >= 0 and right < n 必须写在字符比较之前。 Python 的负下标是合法的，left 变成 -1 时 s[-1] 会静默取到末尾字符，不报错却会把不相邻的两端错判成相等。

样例复核¶

s = "cbbd"，n = 4，起手 start = 0、length = 1。

center=0 奇：(-1, 1) 直接因 left < 0 退出，长度 1 - (-1) - 1 = 1，不更新
         偶：(0, 1) 'c' 与 'b' 不等，长度 1 - 0 - 1 = 0，不更新
center=1 奇：(0, 2) 'c' 与 'b' 不等，长度 1，不更新
         偶：(1, 2) 'b' == 'b' -> 扩到 (0, 3)，'c' 与 'd' 不等退出，
             长度 3 - 0 - 1 = 2 > 1 -> start = 1, length = 2
后续中心都扩不出更长的

返回 s[1:3] = "bb"，与期望输出一致。

参考实现¶

solutions/leetcode/LC5/sol.py
from typing import List, Optional


class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s                        # 空串或单字符本身就是答案，省掉后面的整趟循环
        # 记起点与长度而不是只记长度：题目要的是子串本身，光有长度还原不出来。
        # length 起手取 1（题面保证串非空，答案至少一个字符）；取 0 会让 "abcd" 返回空串
        start, length = 0, 1
        for center in range(n):
            # 两类中心都要枚举，共 2n-1 个：
            #   (center-1, center+1) 是奇数长度的回文，轴是 s[center]，起手就跳过轴本身
            #   (center, center+1)   是偶数长度的回文，轴落在两字符之间的缝里
            # 只做其中一类会漏答案："cbbd" 缺了偶数中心就只能返回 "c"
            for left, right in ((center - 1, center + 1), (center, center + 1)):
                # 边界判断必须在字符比较之前：Python 的负下标合法，
                # left = -1 时 s[-1] 会静默取到末尾字符，把不相邻的两端错判成相等
                while left >= 0 and right < n and s[left] == s[right]:
                    left -= 1
                    right += 1
                # 退出时 left、right 已经越过回文两端，真正的回文是开区间 (left, right)：
                # 长度 right - left - 1，起点 left + 1。写成 right - left 会多算 2
                cur = right - left - 1
                # 必须是严格大于：写成 >= 会让同样长的后来者顶掉先到者，
                # "babad" 会返回 "aba" 而不是期望的 "bab"
                if cur > length:
                    start, length = left + 1, cur
        return s[start:start + length]      # 右端点是开区间，加 1 会多带一个字符

LC5 最长回文子串¶