1. 先看清第 5 题在问什么：不是“判断回文”，而是“找全部回文中最长的那段”
刷 LeetCode Hot 100 的同学应该都有这样的体验：第 5 题“最长回文子串”看起来人畜无害，毕竟判断一个字符串是不是回文，谁都会写——左右两个指针往中间一夹就行。可一旦要求“返回字符串 s 里的最长回文子串”，事情就变了：你需要在一大堆子串里挑出最长的那段，而不是只判断某一小段成不成立。这个区别，恰恰就是这道题被放进 Hot 100、并且排得还比较靠前的原因。
题目原文很简单：给你一个字符串s，找到s中最长的回文子串。比如s = "babad"，答案是"bab"或者"aba"都可以；s = "cbbd"，答案是"bb"。注意一个子串必须是连续截取的一段，不能跳着选字符。很多人一开始容易把“最长回文子序列”和它搞混，子序列才允许跳字符，那是另一道题，后面我会展开说。
那这道题的隐藏考点是什么？我认为有三个：第一是对称性的理解，回文串本质上就是一个关于中心对称的结构；第二是重复比较的消除，不管你用哪种主流解法，核心都是在想怎么少做无用功；第三是复杂度的权衡，暴力做法能过小数据，但数据一旦上千，立刻卡死。Hot 100 把它排在第 5 位，并不是因为它难到劝退，而是因为它把字符串处理、动态规划、双指针思想全串起来了，非常适合作为刷题进阶的第一道坎。
前置知识其实很少：你只需要知道什么是回文串、会写基本的循环和s[i]取字符就行。但如果你想在面试里优雅地讲清楚三种解法（中心扩展、动态规划、Manacher），那就还需要对“对称信息如何复用”有一个直观的感觉。这篇文章我就按我自己刷这道题的路径来写：先从最暴力的思路说起，再一步步看到它怎么变成 O(n^2) 的中心扩展，又怎么变成一张 DP 表格，最后再谈谈真正能做到 O(n) 的 Manacher 算法。每一段我都会把当时的困惑、踩过的坑和现在回头看觉得“早知道就好了”的点放进去。
2. 暴力三层循环为什么是“思路陷阱”：从 O(n^3) 到 O(n^2) 的关键一步
很多人拿到这道题的第一反应是：枚举所有子串，逐个判断是不是回文，取最长的那个。这个思路逻辑上完全正确，但它会把复杂度直接拉到 O(n^3)，在 LeetCode 上s长度稍微到几百、几千就过不去了。问题不在于“判断回文”本身慢，而在于你要判断的子串数量太多了。
简单算一笔账：一个长度为 n 的字符串，子串的起点有 n 种选择，终点也有约 n 种选择，光枚举所有子串就是 O(n^2) 的规模；对每个子串再用双指针判断一次回文，每次要 O(n)。乘在一起就是 O(n^3)。n = 100 时是 10^6 次操作，勉强能忍；n = 1000 时是 10^9 次，已经非常吃力；n = 10^5 时就是 10^15 次，现代计算机也得跑到地老天荒。
那么第一个真正有用的优化转折点在哪？在于别再枚举“子串”，改成枚举“对称中心”。
你观察一下：任何一个回文串，不管它多长，都有一个对称中心。奇数长度的回文串，中心是正中间那个字符，比如"aba"的中心是'b'；偶数长度的回文串，中心是中间两个字符之间的那道空隙，比如"abba"的中心在'b'和'b'中间。一个长度为 n 的字符串里，能作为对称中心的位置有多少个？字符本身有 n 个，字符之间的空隙有 n-1 个，合起来是 2n-1 个。枚举每一个中心，再从这个中心向左右两边同时扩展，只要左右字符相等就继续扩，直到不能扩为止。每个中心最多扩展 n 次，于是总复杂度是 O(2n * n) = O(n^2)。
这一步的思想其实特别朴素：回文串不是“从两端向中间”生成的，而是从中心向两边长出来的。你把判断的重点从“这个子串整体是否回文”换成了“以这个位置为中心能长出多长的回文”，一下子就把每个子串的重复判断分摊掉了。这也是我觉得暴力和中心扩展之间最本质的分界线——不是代码量的问题，而是你有没有意识到“对称中心”才是回文问题的最小单位。
| 解法 | 时间复杂度 | 空间复杂度 | 适合场景 |
|---|---|---|---|
| 暴力枚举子串 | O(n^3) | O(1) | 只用来理解题意 |
| 中心扩展 | O(n^2) | O(1) | 面试首选主解 |
| 动态规划 | O(n^2) | O(n^2) | 需要迁移到其他回文题 |
| Manacher | O(n) | O(n) | 大数据量、追求最优 |
很多教程会把中心扩展当成“面试最推荐写法”，原因就在空间上：你只需要两个指针做扩展，不需要额外开表，就可以拿到最优解的同数量级复杂度。动态规划虽然也是 O(n^2)，但要开一个 n*n 的二维数组，讨论起来多一层负担。所以在面试里，我的建议顺序永远是：先写中心扩展，讲清楚它比暴力好在哪；如果时间富余，再补一下 DP；Manacher 可以提思路，不一定强求写成代码。
3. 中心扩展法：面试中的主力解法，代码短且空间为 O(1)
中心扩展法的实现并不长，但很多第一次写的人会在“奇数长度和偶数长度怎么统一处理”上卡住。我的建议是：干脆不要试图去统一，写一个辅助函数expand(left, right)，它接收两个初始下标，代表当前中心在哪个位置，然后不断向两边扩展。如果回文中心是一个字符，就传(i, i)；如果中心是字符之间的空隙，就传(i, i + 1)。这样奇数、偶数天然都覆盖了，不需要额外的 if 分支。
这里有一个我当年踩过的小坑：辅助函数返回的长度到底是什么？如果你直接返回right - left + 1，那是在 while 退出前最后一次合法扩展的位置。但更稳妥的做法是让 while 循环先走到不满足条件，然后再返回最终的实际匹配长度。写成代码就是这样：
def longestPalindrome(s: str) -> str: if not s: return "" n = len(s) start, end = 0, 0 def expand(left: int, right: int) -> int: while left >= 0 and right < n and s[left] == s[right]: left -= 1 right += 1 # 退出 while 时，left 和 right 已经越界一位 # 实际匹配长度是 right - left - 1 return right - left - 1 for i in range(n): len1 = expand(i, i) # 奇数长度回文 len2 = expand(i, i + 1) # 偶数长度回文 cur_max = max(len1, len2) if cur_max > end - start: start = i - (cur_max - 1) // 2 end = i + cur_max // 2 return s[start:end + 1]我重点解释一下最后更新start和end的两个公式，因为很多人背下来了但不知道为什么。比如expand(i, i + 1)表示中心在s[i]和s[i+1]之间的那道空隙，我们统一用i来代表这个中心的位置。假设最终得到的最长回文长度是cur_max，那么这段回文的左端点应该是i - (cur_max - 1) // 2，右端点是i + cur_max // 2。
为什么是这个式子？你可以代入两个例子验证。字符串"cbbd"，最长回文是"bb"，长度为 2，中心空隙在i = 1处。左端点1 - (2-1)//2 = 1 - 0 = 1，右端点1 + 2//2 = 2，所以返回s[1:3]，正好是"bb"。再看"babad"，最长回文长度是 3，比如i = 1时向两边扩展得到"bab"。左端点1 - (3-1)//2 = 0，右端点1 + 3//2 = 2，返回s[0:3]，正确。这个公式的妙处在于，它利用整除的向下取整把奇偶长度统一了。你不需要分情况讨论，记住这个式子就行。
那有哪些地方特别容易写错？我列几个真实遇到的：
- 忘记处理空串。如果
s = ""，直接返回空字符串，别让循环去访问s[0]。 - 把
end - start和cur_max比较时，要注意end是闭区间的右端点，所以当前记录到的长度是end - start，不是end - start + 1。我第一次写的时候这里多加了 1，结果返回的字符串老是长一截。 expand内的 while 条件一定要先判断边界，比如left >= 0和right < n要写在前，否则下标一越界就IndexError。- 在 Python 里，
(cur_max - 1) // 2当cur_max是偶数时，其实得到的是cur_max / 2 - 1，这恰好让左端点往左多让一位；当cur_max是奇数时，得到的是cur_max // 2。所以它天然兼容两种长度，这也是为什么我一直推荐用这个写法而不是分开写 if。
说句实在话，中心扩展法在面试中已经算“够用且优秀”的答案了。时间复杂度 O(n^2) 在绝大多数笔试和面试场景里都能通过，空间复杂度又只有 O(1)，你完全可以把更多精力放在为什么它是对的、时间复杂度怎么推导上。如果你只准备一种解法应付这道题，我会毫不犹豫推荐它。
4. 动态规划解法：把“是否回文”变成一张可复用的表
动态规划的切入点不太一样：它不关注“某个中心能扩展多远”，而是用一张二维表dp[i][j]记录“子串s[i..j]是不是回文”。换句话说，我们把“每个子串是否是回文”这个问题的答案缓存下来，后面再用的时候直接查表。
状态转移其实很漂亮。dp[i][j]要成立，需要满足两个条件：第一，s[i]等于s[j]，首尾字符相同；第二，去掉首尾之后剩下的内部子串s[i+1..j-1]也必须是回文，或者这个子串足够短，比如长度是 0 或 1，那自然就是回文。写成转移式就是：
if s[i] != s[j]: dp[i][j] = False else: if j - i < 3: dp[i][j] = True else: dp[i][j] = dp[i + 1][j - 1]这里j - i < 3这个条件可能有点绕。它表示子串长度j - i + 1小于等于 3：长度为 1 时左右边界相同（同一个字符），长度为 2 时两个字符相等就是回文，长度为 3 时首尾相等、中间只有一个字符，也肯定是回文。所以这三个长度根本不需要查表，直接置 True 就行。我之前见过有人写成j - i <= 2，其实和j - i < 3完全等价，都可以。
完整实现如下：
def longestPalindrome(s: str) -> str: n = len(s) if n < 2: return s dp = [[False] * n for _ in range(n)] for i in range(n): dp[i][i] = True start = 0 max_len = 1 for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 if s[i] != s[j]: dp[i][j] = False else: if j - i < 3: dp[i][j] = True else: dp[i][j] = dp[i + 1][j - 1] if dp[i][j] and length > max_len: start = i max_len = length return s[start:start + max_len]这里有一个初学者特别容易踩的坑：为什么外层循环要先按length枚举，再枚举起点i？原因是dp[i][j]依赖的是dp[i+1][j-1]，也就是长度短 2 的那个子串。如果你按常规的i从前往后、j从后往前的顺序填表，可能你在算dp[i][j]的时候，dp[i+1][j-1]还没被算出来。所以必须保证“更短的子串先被更新”，最直接的办法就是外层枚举长度，内层枚举起点。
当然，也不是没有别的遍历方式。你还可以让i从n-1往0走，内层j从i+1往n走，这样dp[i+1][j-1]所在的下一行已经算过了，也能保证正确。很多题解里的写法是前者，面试时只要能讲清楚“依赖顺序”这一点，两种写法都是可以接受的。
动态规划解法的优点是思路统一，尤其适合变种题。比如后面要统计回文子串的个数，用 DP 表格可以顺手计数；比如最长回文子序列，那更是直接套区间 DP 的框架。缺点是空间复杂度高，O(n^2) 的二维数组在n = 10^5时根本开不出来。所以如果你只为了做 LeetCode 5 这一道题，DP 不如中心扩展省事；但如果你想通过这一题顺便打通后面好几道回文题，DP 是值得熟练掌握的。
空间优化可以做到一维滚动数组，因为dp[i][j]只依赖更短的区间结果。但我的个人建议是，面试时不要轻易把代码优化成滚动数组，因为一旦你开始“滚动”，你就不再保留所有子区间的答案了，如果题目要求最后输出具体子串，记录起始位置会变得特别容易出错。先用二维表把正确性讲清楚，如果面试官追问能不能降空间，你再提“可以用滚动数组优化到 O(n)，但为了保持可读性先不写了”，这是一个很得体的应对方式。
5. Manacher：线性时间算法，究竟“快”在哪儿
如果面试官继续追问，或者笔试数据量特别大，比如长度达到 10^6，O(n^2) 的算法就扛不住了。这时候就需要 Manacher 算法，它能把找最长回文子串的复杂度降到 O(n)。我第一次看到这个算法的时候，觉得它像魔法：明明每个中心都需要向两边扩展，怎么可能线性完成？后来才明白，它本质上是在“利用已经算好的对称信息做跳跃”，而不是从头扩展。
先看预处理。Manacher 会把原始字符串扩展成一个所有回文中心都变成“单一字符位”的形式：在字符串的首尾和每个字符之间插入一个特殊字符。常见做法是：
t = '#' + '#'.join(s) + '#'比如"babad"就变成"#b#a#b#a#d#"。为什么要这么干？因为原来的字符串里，奇数长度回文的中心是字符，偶数长度回文的中心是空隙，两种中心类型不一致。插入#之后，所有回文串在t里都变成了奇数长度，中心位置要么是原始字符、要么是插入的#，统一处理起来非常方便。更精细的写法会在首尾再加上^和$，用来当哨兵，防止 while 扩展的时候频繁判断数组越界：
t = '^#' + '#'.join(s) + '#$'接下来定义数组P[i]，它表示以t[i]为中心、往两边扩展时能匹配到的不含中心本身的半径长度。然后我们维护两个关键变量：center和right。right表示当前扫描过程中，所有已知回文串里能到达的最右边界；center就是产生这个最右边界的那一个中心。这两个变量是整个算法的灵魂。
Manacher 的核心复用逻辑可以描述成一句话：如果当前枚举的中心i还在已知回文区间内部，也就是i < right，那i关于center的镜像位置mirror = 2 * center - i的半径早就已经算过了，P[i]可以直接取min(P[mirror], right - i)作为初始值。这个初始值不是乱猜的，它来源于回文的中心对称性：在center这一圈回文里，i和mirror完全对称，所以mirror能匹配的字符，i大概率也能匹配。但镜像的半径可能超出center已知回文的左边界，超出部分不能保证，所以我们用right - i把它截断。
打个比方，这就像你抄别人已经做好的作业：镜像点mirror已经把左半边的情况摸清楚了，你想知道i这边最少是多少，可以直接“抄”过来，但抄的范围不能超过已知答案的边界。超出边界之后，还得老老实实自己扩展验证。这也是我经常推荐学生用“抄作业但不超过答案边界”来理解 Manacher 的原因，非常直观。
完整代码我贴一个能直接跑的版本：
def longestPalindrome(s: str) -> str: t = '#'.join('^{}$'.format(s)) n = len(t) p = [0] * n center = 0 right = 0 for i in range(1, n - 1): if i < right: mirror = 2 * center - i p[i] = min(right - i, p[mirror]) while t[i + p[i] + 1] == t[i - p[i] - 1]: p[i] += 1 if i + p[i] > right: center = i right = i + p[i] max_len = 0 center_idx = 0 for i in range(1, n - 1): if p[i] > max_len: max_len = p[i] center_idx = i start = (center_idx - max_len) // 2 return s[start:start + max_len]这里的p[i]表示的是“不含中心本身的扩展半径”，所以最终最长回文子串的原始长度和p[i]是有对应关系的。最后计算start的时候，用(center_idx - max_len) // 2，很多第一次写的人会漏掉这个细节，算出来是负数或者偏差一位。我建议自己拿"babad"和"cbbd"各跑一遍，把t数组的下标写出来，你就能很清楚它为什么成立。
那为什么说它是线性时间？关键在于right是只增不减的。while 循环每扩展成功一次，right就会往右推进一次；整个算法过程中right从 0 最多推进到 n，所以所有 while 操作的总次数是 O(n)。再加上每个下标本身只遍历一次，总复杂度就是 O(n)。这也是 Manacher 最漂亮的地方：它把原本每个中心都要“从头扩展”的 O(n^2) 工作，借助对称性压缩成了 O(n)。
不过我还是要说一句实在话：Manacher 属于那种“原理懂了很好，但代码细节特别容易写岔”的算法。如果你在面试里能完整写出中心扩展法，并且能大概讲清楚 Manacher 的right、center、mirror三位一体的思路，已经足够拿一个不错的评价。如果面试官要求你现场写完整的 Manacher，而且你一时写不顺，坦诚地说“这个算法我更多是理解思路，边界和下标细节需要再推一下”，往往比硬着头皮写一个出错的版本更好。
6. 从这道题延伸开的高频变体与刷题节奏建议
最长回文子串不是孤立的题。刷完它，你会发现在 LeetCode 和面试题里有一批和它长相相似、解法却微有不同的题目。提前搞清楚它们之间的差异，比单纯背一道题的代码有用得多。
最直接的变体是LeetCode 647 回文子串个数。它问的不是最长回文子串，而是字符串里一共有多少个回文子串。这道题用中心扩展法非常顺手，因为你每从一个中心向外成功扩展一次，就相当于发现了一个新的回文子串，直接计数就行。如果你非要先算完所有回文子串再去统计，那就绕远了，还会多开一个二维数组。这就是中心扩展法优于动态规划的一个典型场景。
另一个常见变体是LeetCode 516 最长回文子序列。注意“子序列”和“子串”的区别：子串必须连续，子序列可以跳着选字符。一旦允许跳字符，中心扩展法和 Manacher 就都不能用了，因为你没法再靠“向两边逐字符比较”来判断对称关系。这类题要用区间 DP：dp[i][j]表示s[i..j]中最长回文子序列的长度，转移时看s[i]和s[j]是否相等，如果相等就是dp[i+1][j-1] + 2，不相等就取max(dp[i+1][j], dp[i][j-1])。这种“连续 vs 不连续”的判断，是我觉得回文题里最容易混淆的地方。
面试中还经常出现一种小变体：给你一个字符串，问能否通过最多删除一个字符让它变成回文。这道题不需要动态规划，双指针从两端往中间扫，第一次遇到左右不相等的时候，检查跳过左边或者跳过右边之后剩下的内部子串是否是回文即可。它看起来也是回文题，但解法已经完全不是一回事了。所以你看，回文这个主题底下其实藏着好几种问题模型，搞懂“连续”和“不连续”、搞懂“求最长”和“判断可行”，要比单纯刷题有用得多。
回到 LeetCode 5 本身，我建议的刷题节奏是这样的：第一天先把中心扩展法写熟练，能用它解释清楚为什么是 O(n^2)；第二天可以自己推导动态规划版本，重点理解遍历顺序；第三天或者后面有空，再去啃 Manacher。不用急着一天之内拿下所有解法，那样很容易变成“背代码”，而不是“理解算法”。我刷这道题前后三遍，每一遍都有新感受：第一遍惊险 AC 但没理解为什么中心扩展能替代暴力；第二遍写 DP 时理解了子区间递归的依赖；第三遍看 Manacher 才真正体会到“对称信息复用”这个底层思维的价值。
最后分享一个小经验：遇到“最长 XX 子串/子序列”类的问题，先别急着套模板，先问自己三个问题——要求连续还是不连续？要求返回内容还是只返回长度？数据规模有多大？把这三个问题想清楚再选解法，基本不会走偏。
