LeetCode 5. 最长回文子串：中心扩展的直觉与边界

最长回文子串（LeetCode 5，Medium）是回文系列的第一道正餐：给一个字符串，找出其中最长的回文子串。它难在两个地方：回文的「奇偶」两种形态带来恼人的边界，以及多种解法的取舍容易让人迷失。本篇从暴力讲起，走一遍动态规划，最后落在面试中最实用的中心扩展法——顺便一瞥传说中的 Manacher 线性算法长什么样。

解法一：暴力与它的困境

最直白的思路：枚举所有子串（起点 i、终点 j 两重循环），逐个判断是否回文（再一重循环），记录最长的。三重循环，时间 O(n³)——对 n=1000 的输入是十亿次操作，超时无疑。它的价值是当「对拍基准」：写正式解法前先用暴力实现，随机小数据对拍验证正确性——这是本库反复强调的「本地跑通」纪律的第一步。小幅优化可以到 O(n²) 时间 O(n²) 空间：用动态规划预处理「i..j 是否回文」的布尔表——dp[i][j] = (s[i]==s[j]) and dp[i+1][j-1]，按子串长度从短到长填表。这张表空间 O(n²)，对长字符串内存压力大；而且它的信息（所有回文子串）超出了题目需要（只要最长那个）——空间可以更省，时间可以不变，这就是中心扩展。

解法二：中心扩展——从每个「中心」向两边长

核心直觉：每个回文都有一个「中心」——奇数长度回文的中心是一个字符（aba 的 b），偶数长度回文的中心是两个字符之间的缝隙（abba 的中间）。枚举所有可能的中心（n 个字符 + n-1 个缝隙 = 2n-1 个），从每个中心向两边扩展，直到字符不再相等，记录最长的回文。每个中心的扩展最多 O(n)，总时间 O(n²)，空间 O(1)——空间是它相对 DP 表的压倒性优势。实现的关键是处理奇偶：用同一个辅助函数 expand(l, r)，奇数回文传 (i, i)，偶数回文传 (i, i+1)，返回扩展后的边界：

def longest_palindrome(s: str) -> str:
    if not s:
        return ""
    start, end = 0, 0

    def expand(l: int, r: int) -> tuple:
        # 从中心 (l, r) 向两边扩展，返回回文的左右边界
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return l + 1, r - 1   # 循环结束时多走了一步，收回来

    for i in range(len(s)):
        for l, r in (expand(i, i), expand(i, i + 1)):
            if r - l > end - start:
                start, end = l, r
    return s[start:end + 1]

最常见的 bug就在 expand 的返回：循环退出时 l 和 r 已经「多走了一步」（走到了不匹配的位置），返回边界要收回一步（l+1, r-1）——很多人在这里返回了越界或差一位的边界，测试用例 cbbd（答案 bb）一跑就现形。这就是为什么本篇开头说暴力对拍重要：边界错误靠眼睛很难发现，靠对拍一秒现形。

解法三：Manacher 算法的一瞥

中心扩展的 O(n²) 有一个 O(n) 的解法——Manacher 算法，它的核心技巧有两步：第一步，在字符间插入分隔符（aba → #a#b#a#），把奇偶回文统一成奇数长度（消灭边界讨论）；第二步，利用已算出的回文信息——记录当前「右边界最远」的回文，新位置若在回文内，它的最短回文长度可以镜像复制对称位置的已算结果（省去从头扩展），只有越出回文边界时才继续扩展。每个位置最多被扩展 O(1) 次，总时间 O(n)。Manacher 的细节（镜像半径、边界钳制）足以单独成篇，本篇只立路标：面试与日常工程中，中心扩展几乎总是正确选择（代码短、边界清晰、O(n²) 对大多数输入足够）；Manacher 是竞赛与极端性能场景的工具，需要时再学。

本地验证与常见坑

解法代码必须在本地跑通（本库纪律），最小验证集："babad" → "bab" 或 "aba"、"cbbd" → "bb"、"a" → "a"、空串 → 空串、全同字符 "aaaa" → "aaaa"。常见坑清单：奇偶中心的遗漏（只写了奇数扩展，cbbd 挂掉）、expand 返回边界的差一错误、以及更新最长时用长度比较写反（> 写成 >= 会偏向后出现的同长回文——题目说「只需返回一个」，但要对拍确认）。复杂度总结：暴力 O(n³)/O(1)，DP O(n²)/O(n²)，中心扩展 O(n²)/O(1)，Manacher O(n)/O(n)——面试的推荐顺序：先中心扩展（清晰正确），被追问优化再提 Manacher 的思路。

手动模拟：用「babadm」走一遍中心扩展

把算法在纸面上走一遍，是理解边界处理最快的方式。以 babadm（n=6）为例，逐中心模拟：中心 i=0（b）：expand(0,0)——s[0]==s[0] 成立向两侧扩，l=-1 越界停止，返回 (0,0)，回文 "b"；expand(0,1)——s[0]='b' vs s[1]='a' 不等，不扩展，返回 (1,0)——注意这个返回「左大于右」，长度计算 r-l=−1 不会更新答案（这就是 expand 返回值的防御性：无效中心自动产生负长度）。中心 i=2（b，即 bab 的 b）：expand(2,2)——s[1]='a'==s[3]='a' 扩展，s[0]='b'==s[4]='b' 再扩展，s[-1] vs s[5] 越界停止，返回 (0,4)，"babad" 的前缀 "bab"... 等等，返回的是 (0,4) 即 "bab a d"？重新核对：l+1=0, r-1=3，子串 s[0:4]="baba"——不对，"baba" 不是回文！这个卡顿正是模拟的价值：expand 的循环条件是「相等才扩」，退出时 l、r 指向的是不匹配的位置——s[-1] 越界时循环退出，此刻 l=-1, r=5，收一步得 (0,4)="baba"？还是不对——冷静重查：expand(2,2) 的初始 l=2, r=2，s[2]=='s[2]' 成立 → l=1, r=3；s[1]='a'==s[3]='a' → l=0, r=4；s[0]='b'==s[4]='d' 不等 → 退出。返回 (l+1, r-1) = (1, 3)，子串 s[1:4] = "aba" ✓——之前的心算是「边界收回」算错了方向：退出时 l、r 指向不匹配位，收回一步恰好是最后一次匹配的区间。模拟走完，最长回文 "aba" 或 "bab"（长度 3）被正确记录。三分钟的纸面模拟，胜过半小时的脑内纠结。

变体族谱：回文的四张面孔

最长回文子串之后，回文家族还有三张面孔值得认识。面孔一：最长回文子序列（LeetCode 516）——可以删字符的版本（不要求连续），解法从中心扩展切换为区间 DP：dp[i][j] = s[i..j] 内最长回文子序列，转移看两端——相等则 dp[i+1][j-1]+2，不等则 max(dp[i+1][j], dp[i][j-1])——「子串」与「子序列」的一字之差，解法从中心扩展切换为区间 DP（连续性约束的强弱决定方法族）。面孔二：回文子串计数（LeetCode 647）——数所有回文子串的个数，中心扩展的变体（每个中心扩展时每成功扩一步就计数一次，而不是只记录最长）。面孔三：分割回文串（LeetCode 131/132）——把字符串分割成全是回文的方案，回溯 + 回文 DP 表的组合（DP 表预判 i..j 是否回文供回溯剪枝，132 的最少分割次数是区间 DP 的应用）。四张面孔的族谱关系：都是「回文性质 + 不同的目标」——最长子串、最长子序列、计数、分割——回文结构是源代码，题目目标是编译产物。

错误案例集锦：三种典型 WA 的现场还原

最长回文子串的错答案（Wrong Answer）有三种高发现场，逐一还原。WA 之一：只写了奇数中心——代码只有 expand(i, i) 一个调用——用例 "cbbd"：所有奇数中心扩展出的最长回文是 "c" 或 "b"（长度 1），正确答案 "bb" 长度 2——症状是「偶回文全部漏掉」，修复是补上 expand(i, i+1) 的偶中心调用。WA 之二：expand 返回值没收步——写成 return l, r（不收一步）——用例 "babad"：中心 1 扩到 l=-1, r=3，返回 (−1, 3)，长度 r−l=4（虚增），且切片 s[-1:4] 的负下标语义产生诡异的子串——症状是「答案长度虚增或运行时负索引错乱」。WA 之三：无输入的崩溃——空串时 expand 从未被调用、start/end 保持 0，返回 s[0:1] = ""——这个恰好对，但若初始化写成 start, end = 0, 1 就会切片越界或返回错值。三种 WA 的共同预防手段：五个标准用例（babad/cbbd/a/空/全同字符）在写代码之前先列在注释里——先有测试再有实现，是算法题版的 TDD。

工程视角：回文检测在真实系统里的样子

最长回文子串在工程里的真实应用与教科书有落差，值得校准认知。生物信息：DNA 序列中的回文结构（限制性内切酶的识别位点常是回文——生物学的「回文」是双链互补意义上的，与字符串回文形似神异——校准这个认知避免生搬硬套）；文本处理：内容审核中的回文变体检测（规避关键词过滤的字符插入变形——「敏*感」的变体识别需要模糊回文匹配）；编码与压缩：回文结构的压缩利用（对称结构的存储优化）。工程与教材的差距所在：真实文本的「最长回文」往往是无意义的字符巧合（英文里 "elloh" 之类的碎片），Palindromic 长度本身很少是业务目标——业务要的通常是「有意义的回文模式」，即带语义约束的回文匹配——这需要把本篇的纯结构算法与语义规则组合。工程校准的结论：算法是通用的积木，业务把它与语义、阈值、上下文组合——课本给你积木，工程教你拼装。

一个补充：子串 vs 子序列 vs 子数组

回文题的讨论容易混淆三个概念：子串——连续的一段字符；子序列——可以删字符但保持相对顺序；子数组——连续的一段元素。本篇的最长回文子串要求连续，所以中心扩展是天然解法；如果题目改为最长回文子序列（可以删字符），解法就切换为区间 DP——两者一字之差，解法族完全不同。区分这三者的诀窍：看题目允许不允许跳过字符——不允许跳是子串（中心扩展），允许跳是子序列（区间 DP）——这个区分法适用于所有子序列与子串的题目族。

小结

这篇收成四条：回文的中心有两种形态（字符与缝隙），中心扩展用 2n-1 个中心 + expand 函数统一处理，O(n²) 时间 O(1) 空间；expand 返回边界要收回一步——差一错误靠小数据对拍现形；DP 解法（dp[i][j] 定义回文表）思路清晰但空间贵，适合作为理解回文结构的台阶；Manacher 用分隔符统一奇偶 + 镜像复制实现 O(n)，是竞赛工具，面试点到为止。回文系列的下一课，是更难的「最长回文子序列」（子序列版可以删字符），思路将从中心扩展转向区间 DP——那是另一篇的故事。

参考资料

• LeetCode 5. Longest Palindromic Substring —— 题目与官方题解
• Manacher, G. (1975). A new linear-time "on-line" algorithm for finding the longest palindromic substring —— 线性算法的原始论文
• 本库前篇：《LeetCode 15. 三数之和：排序 + 双指针的教科书示范》《LeetCode 42. 接雨水》