题目描述
思路解析
一句话答案：LeetCode 5 最长回文子串的主流解法是中心扩展：回文由中心对称决定，把每个字符和每条相邻缝隙都当作中心（共 2n-1 个），从中心向两边扩到字符不等为止，全程记录最长的一段。时间 O(n²)、空间 O(1)。
最长回文子串在找什么
在字符串 s 中找一段连续的子串，使它正着读和倒着读完全一样，且长度最长，返回这段子串本身。比如 s = "cbbabba" 的答案是 "bbabb"。注意两点：子串必须连续，不是可以跳着选的子序列；答案要的是字符串本身，所以过程中得记住这段回文的起止位置。
为什么逐个检查子串太慢
最笨的办法是枚举所有子串再逐个验证是否回文：子串有 O(n²) 个，每次验证要 O(n)，加起来 O(n³)，字符串一长就没法接受。慢在验证之间毫无信息共享——判断 "bbabb" 时从头比到尾，完全没利用 "bab" 已经是回文这个事实。
其实回文自带一个可用的结构：每个回文都有一个对称中心，从中心向两侧一层层剥开，每层左右字符都相等。反过来，固定中心向外扩，扩到哪里断掉，以它为中心的最长回文就定了。所以换成按中心枚举：每个中心从里往外扩一次，之前从头重验的浪费就没了。
为什么中心有 2n-1 个而不是 n 个
回文分奇偶两种：奇数长度的回文（如 "bab"）中心是一个字符；偶数长度的回文（如 "bb"）中心落在两个相邻字符之间的缝隙上。长度为 n 的字符串有 n 个字符中心、n-1 个缝隙中心，合计 2n-1 个。只枚举字符中心是这题最常见的错误——那样所有偶数长度的回文都找不到，"cbbabba" 里的 "bb"、"abba" 会整批漏掉。
中心扩展每一步为什么是对的
算法过程中始终守着一个不变量（一条自始至终成立的性质）：左右两个位置标记 l、r 能继续向外走，前提是 s[l] 到 s[r] 这一段已经是回文。向外扩一步只新增两端字符，若 s[l-1] 等于 s[r+1]，对称就延续到更大一段；一旦两端不等就停：两端不同的串不可能是回文，再往外扩也救不回来，停下不会漏掉更长的答案。
拿 cbbabba 亲手走一遍
挑两个关键中心走一遍。先看下标 1、2 之间的缝隙：两侧都是 'b'，相等，扩出 "bb"；再往外一层比下标 0 的 'c' 和下标 3 的 'a'，不等，停下，记下 "bb"。真正的答案藏在下标 3 的 'a' 这个奇数中心：自身是 "a"，向外 'b' 对 'b' 扩成 "bab"，再向外 'b' 对 'b' 扩成 "bbabb"，第三层 'c' 对 'a' 不等停下。"bbabb" 长度 5 超过 "bb"，成为最终答案。把 2n-1 个中心都这样过一遍，见过的最长那段就是解。
复杂度多少，哪些边界容易翻车
中心共 2n-1 个，每个最多向外扩约 n/2 层，时间 O(n²)；除了几个下标变量什么都不开，空间 O(1)。另一种同为 O(n²) 的区间动态规划要开二维表记录每段是否回文，中心扩展更省空间也更好写。
边界有三处最容易翻车：扩展循环必须先判 l >= 0 且 r < len(s) 再比较字符，否则越界；截取子串时闭区间长度是 r - l + 1，差一就会截错；若面试官明确要求 O(n)，那是 Manacher（马拉车）算法的领域，复用已经算过的回文半径（每个中心能往外扩多远），实现较复杂，通常在必须线性时才上。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住：枚举每个中心（单字符 + 双字符两种），向两边扩，全程记下最长的那段。下面每一帧都在套它。
换一个中心：以单个字符 'c'（下标 0）为中心，这会撑出奇数长度的回文。让 l、r 都从这里出发向两边扩。
两端 s[0]='c' 和 s[0]='c' 相等，说明 "c" 是回文。但没有超过当前最长 "c"。继续向两边各扩一格。
指针扩到字符串边界外了，对称被打破，这个中心扩展结束。当前记录到的最长回文是 "c"。
换一个中心：以下标 0 和 1 之间的间隙为中心（偶数长度）。先比相邻这两个字符 'c' 与 'b'，不相等，这个中心扩不出回文，跳过。
两端 'c' 和 'b' 不再相等，对称被打破，这个中心扩展结束。当前记录到的最长回文是 "c"。
换一个中心：以单个字符 'b'（下标 1）为中心，这会撑出奇数长度的回文。让 l、r 都从这里出发向两边扩。
两端 s[1]='b' 和 s[1]='b' 相等，说明 "b" 是回文。但没有超过当前最长 "c"。继续向两边各扩一格。
两端 'c' 和 'b' 不再相等，对称被打破，这个中心扩展结束。当前记录到的最长回文是 "c"。
换一个中心：以下标 1 和 2 之间的间隙为中心（偶数长度）。先比相邻这两个字符 'b' 与 'b'，相等，可以开始扩。
两端 s[1]='b' 和 s[2]='b' 相等，说明 "bb" 是回文。它比之前的最长还长，更新最长记录为 "bb"（标绿）。继续向两边各扩一格。
两端 'c' 和 'a' 不再相等，对称被打破，这个中心扩展结束。当前记录到的最长回文是 "bb"。
换一个中心：以单个字符 'b'（下标 2）为中心，这会撑出奇数长度的回文。让 l、r 都从这里出发向两边扩。
两端 s[2]='b' 和 s[2]='b' 相等，说明 "b" 是回文。但没有超过当前最长 "bb"。继续向两边各扩一格。
两端 'b' 和 'a' 不再相等，对称被打破，这个中心扩展结束。当前记录到的最长回文是 "bb"。
换一个中心：以下标 2 和 3 之间的间隙为中心（偶数长度）。先比相邻这两个字符 'b' 与 'a'，不相等，这个中心扩不出回文，跳过。
两端 'b' 和 'a' 不再相等，对称被打破，这个中心扩展结束。当前记录到的最长回文是 "bb"。
换一个中心：以单个字符 'a'（下标 3）为中心，这会撑出奇数长度的回文。让 l、r 都从这里出发向两边扩。
两端 s[3]='a' 和 s[3]='a' 相等，说明 "a" 是回文。但没有超过当前最长 "bb"。继续向两边各扩一格。
两端 s[2]='b' 和 s[4]='b' 相等，说明 "bab" 是回文。它比之前的最长还长，更新最长记录为 "bab"（标绿）。继续向两边各扩一格。
两端 s[1]='b' 和 s[5]='b' 相等，说明 "bbabb" 是回文。它比之前的最长还长，更新最长记录为 "bbabb"（标绿）。继续向两边各扩一格。
两端 'c' 和 'a' 不再相等，对称被打破，这个中心扩展结束。当前记录到的最长回文是 "bbabb"。
换一个中心：以下标 3 和 4 之间的间隙为中心（偶数长度）。先比相邻这两个字符 'a' 与 'b'，不相等，这个中心扩不出回文，跳过。
两端 'a' 和 'b' 不再相等，对称被打破，这个中心扩展结束。当前记录到的最长回文是 "bbabb"。
换一个中心：以单个字符 'b'（下标 4）为中心，这会撑出奇数长度的回文。让 l、r 都从这里出发向两边扩。
两端 s[4]='b' 和 s[4]='b' 相等，说明 "b" 是回文。但没有超过当前最长 "bbabb"。继续向两边各扩一格。
两端 'a' 和 'b' 不再相等，对称被打破，这个中心扩展结束。当前记录到的最长回文是 "bbabb"。
换一个中心：以下标 4 和 5 之间的间隙为中心（偶数长度）。先比相邻这两个字符 'b' 与 'b'，相等，可以开始扩。
两端 s[4]='b' 和 s[5]='b' 相等，说明 "bb" 是回文。但没有超过当前最长 "bbabb"。继续向两边各扩一格。
两端 s[3]='a' 和 s[6]='a' 相等，说明 "abba" 是回文。但没有超过当前最长 "bbabb"。继续向两边各扩一格。
指针扩到字符串边界外了，对称被打破，这个中心扩展结束。当前记录到的最长回文是 "bbabb"。
换一个中心：以单个字符 'b'（下标 5）为中心，这会撑出奇数长度的回文。让 l、r 都从这里出发向两边扩。
两端 s[5]='b' 和 s[5]='b' 相等，说明 "b" 是回文。但没有超过当前最长 "bbabb"。继续向两边各扩一格。
两端 'b' 和 'a' 不再相等，对称被打破，这个中心扩展结束。当前记录到的最长回文是 "bbabb"。
换一个中心：以下标 5 和 6 之间的间隙为中心（偶数长度）。先比相邻这两个字符 'b' 与 'a'，不相等，这个中心扩不出回文，跳过。
两端 'b' 和 'a' 不再相等，对称被打破，这个中心扩展结束。当前记录到的最长回文是 "bbabb"。
换一个中心：以单个字符 'a'（下标 6）为中心，这会撑出奇数长度的回文。让 l、r 都从这里出发向两边扩。
两端 s[6]='a' 和 s[6]='a' 相等，说明 "a" 是回文。但没有超过当前最长 "bbabb"。继续向两边各扩一格。
指针扩到字符串边界外了，对称被打破，这个中心扩展结束。当前记录到的最长回文是 "bbabb"。
把每个中心都扩过一遍后，见过的最长回文就是答案 "bbabb"（标绿这一段）。
单字符、无更长回文、整串全相同这几种边界都要能正确返回。
两个高频追问：和 DP 的取舍，以及如何降到线性。
参考代码
def longestPalindrome(s: str) -> str: start, end = 0, 0 def expand(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)): l1, r1 = expand(i, i) # 奇数中心 l2, r2 = expand(i, i + 1) # 偶数中心 if r1 - l1 > end - start: start, end = l1, r1 if r2 - l2 > end - start: start, end = l2, r2 return s[start:end + 1]复杂度
- 时间：O(n²)，n 个位置 × 每个中心最多向两边扩 n/2
- 空间：O(1)，只用几个下标变量，不开额外数组
易错点
面试追问把动画讲成自己的话
追问中心扩展和动态规划相比怎么选？
追问要做到 O(n) 怎么办？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
回文子串
LeetCode 647 · 中等 · 沿着 一维动态规划 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题