BM73　最长回文子串¶

中等通过率 35.19%python3核心代码模式样例通过牛客 AC字符串动态规划

牛客原题　源码

讲解章节：回文

一句话

枚举回文中心向两边扩张，取最长的一次扩张长度。

解题思路¶

这题考什么¶

回文串的定义性质是「关于中心对称」，这条性质直接给出一个降维的枚举方式：不枚举左右端点（O(n^2) 对），只枚举中心（O(n) 个），再从中心往外扩到扩不动为止。回文的系统讨论见回文。

中心分两类，一共 2n-1 个：

奇数长度：中心是单个字符 A[c]，从 (c-1, c+1) 这对邻居开始比
偶数长度：中心是两个字符之间的缝隙，从 (c, c+1) 开始比

扩张就是一个循环：

while l >= 0 and r < n and A[l] == A[r]:
    l -= 1; r += 1

退出时 l、r 各自已经多走了一格（越界或字符不等），所以真正的回文区间是 [l+1, r-1]，长度 r - l - 1。取所有中心的最大值即答案。

也可以写成区间 DP：dp[i][j] 表示 A[i..j] 是否回文，

dp[i][j] = (A[i] == A[j]) and (j - i < 2 or dp[i+1][j-1])

时间同为 O(n^2)，但要开一张 n*n 的表，空间 O(n^2)，还多出二维列表的寻址开销；中心扩张只用两个下标，空间 O(1)，正好命中题面要求。真要做到 O(n) 还有 Manacher 算法，本题 n <= 1000 用不上它的复杂度优势。

数据规模与复杂度¶

1 <= n <= 1000，时限 2 秒（其他语言）。 2n-1 个中心，每个至多扩 n/2 步，最坏 O(n^2) = 1e6 次字符比较—— 最坏数据正是「全同字符」串，每个中心都能扩到底。空间 O(1)，只用 l、r、best 三个整数。

坑在哪¶

偶数长度的中心不能漏。只枚举单字符中心时 "abba" 会被答成 1，因为它的对称轴落在两个 'b' 之间，不在任何字符上。
长度公式是 r - l - 1，不是 r - l + 1。循环退出时 l、r 已经各自越过边界一格，少减这个 2 会把每个答案都放大 2。
奇数中心从 (c-1, c+1) 起手而不是 (c, c)：单个字符自己必然回文，没必要拿 A[c] 和自己比一次；起始长度 r - l - 1 已经等于 1。
best 初值取 1 而不是 0：n >= 1 时任何单个字符都是长度 1 的回文。 n < 2 时直接返回 n，同时覆盖了 n = 0 与 n = 1。
扩张的越界判断必须写在字符比较之前，靠 Python 的短路求值挡住 A[-1]—— 负下标不会报错，只会悄悄绕到串尾，把不相邻的字符判成对称。

样例复核¶

"ababc"：c = 1 的奇数中心扩出 "aba"（l = -1、r = 3，长度 3）， c = 2 的奇数中心扩出 "bab"，其余中心都不超过 3，答案 3，与期望输出一致。

参考实现¶

solutions/nowcoder/BM73/sol.py
from typing import List, Optional


class Solution:
    def getLongestPalindrome(self, A: str) -> int:
        n = len(A)
        if n < 2:
            return n                    # 空串答 0，单字符答 1，同时保证下面 best = 1 成立

        best = 1                        # n >= 2 时至少有单字符回文，初值取 1
        for c in range(n):
            # 奇数长度：以 A[c] 为轴。A[c] 自己必然回文，所以直接从它的两个邻居开始比
            l, r = c - 1, c + 1
            # 越界判断写在字符比较之前：Python 的负下标会绕到串尾，短路求值才能挡住
            while l >= 0 and r < n and A[l] == A[r]:
                l -= 1
                r += 1
            # 退出时 l、r 各多走一格，真正的回文是 [l+1, r-1]，长度 r-l-1
            if r - l - 1 > best:
                best = r - l - 1

            # 偶数长度：以 A[c] 与 A[c+1] 之间的缝隙为轴；c = n-1 时 r 越界，循环直接不进
            l, r = c, c + 1
            while l >= 0 and r < n and A[l] == A[r]:
                l -= 1
                r += 1
            if r - l - 1 > best:
                best = r - l - 1        # 两类中心共 2n-1 个，缺一类就会漏掉一半答案

        return best

BM73 最长回文子串¶