题目
给你一个字符串
s，找到
s 中最长的回文子串。
输入: s = "babad"
输出: "bab" （"aba" 同样符合题意）
输入: s = "cbbd"
输出: "bb"
回文串是正着读和反着读都一样的字符串。题面保证
s 至少含一个字符（最短答案就是单字符）。
一、核心洞察：枚举中心，不是枚举子串
先算一笔暴力账：子串有
O(n²) 个（n 个起点 × n 个终点 / 2），每个验证回文要
O(n) —— 总共
O(n³)，n = 1000 就是十亿次起步。
换个视角：
回文是关于中心对称的。如果一个子串是回文，它完全由"中心 + 半径"决定。
所以答案 = 所有中心里扩展出的最长回文 —— 中心只有 2n - 1 个，
每个中心向两边扩展最多 O(n) 步，总时间 O(n²)、空间 O(1)。
这个
2n - 1 是全题最重要的数字。为什么不是
n 个中心？因为
回文有两种长度奇偶：
只写 expand(i, i) 就漏掉了所有偶数回文 ——
"abba"、
"cbbd" 的中心不在任何字符上，在两个字符之间的
间隙里。这是本题最经典的 bug，没有之一。
二、拆解：2n-1 个中心与两种扩展
2.1 扩展怎么写
def expand(s, l, r):
# 从 [l, r] 向两边扩到不能再扩，返回边界
while l > 0 and r < len(s) - 1 and s[l - 1] == s[r + 1]:
l -= 1
r += 1
return l, r
注意扩展的写法是
先假设中心合法，再看两边能不能再长 —— 循环里检查的是
s[l-1] == s[r+1]（往外长一格），不是
s[l] == s[r]（那是收缩前的比较对象，会差一位）。
2.2 主流程：交错枚举
def longestPalindrome(s: str) -> str:
n = len(s)
best_l, best_r = 0, 0
for i in range(n):
# 字符中心：奇数回文
l, r = expand(s, i, i)
if r - l > best_r - best_l:
best_l, best_r = l, r
# 间隙中心：偶数回文（i 与 i+1 之间；s[i] != s[i+1] 时天然构不成）
if i + 1 < n and s[i] == s[i + 1]:
l, r = expand(s, i, i + 1)
if r - l > best_r - best_l:
best_l, best_r = l, r
return s[best_l:best_r + 1]
两个细节：
- 间隙中心先判
s[i] == s[i+1]：不相等就不用扩展（最小的偶数回文都构不成）；
- 同长度先到先得：
> 而不是 >=，"babad" 先扫到 "bab"（起点更靠左），"aba" 不更新 —— 两种答案都对，但返回一个就够。
三、动画怎么看
动画是一行字符格子，扫过
"babad" 的全部 9 个中心（5 字符 + 4 间隙，交错出现）：
- 字符中心帧：中心格橙框，扩展出的区间淡金底；
- 间隙中心帧：两条格之间的竖虚线标记中心位置 ——
"babad" 里所有间隙都构不成偶数回文（两侧字符不等），虚线一闪就过；换成 "cbbd" 就能看到间隙扩展出 "bb"；
- best 下划线：当前全局最优回文下面一条金线，随扫描推进；
- done 帧：最优区间格子变绿，横幅给出答案字符串。
看点是
间隙虚线的"空扫" —— 它们不是浪费：正是这些"长度 0"的帧，保证了偶数回文不会漏。
四、完整推演表
以
"babad" 为主例（9 个中心，交错）：
对照偶数例子
"cbbd"（7 个中心）：字符中心
c/
b/
d 都是长度 1，
间隙 s[1]|s[2]（b 与 b 相等）扩展出 [1, 2] 即 "bb" —— 这就是题面第二个示例的答案来源。而
"abba"：间隙
s[1]|s[2] 相等后还能继续往外扩（
s[0] == s[3]），到
[0, 3] 的
"abba"。
五、变体：DP 对照与 Manacher
5.1 区间 DP（对照解法）
dp[i][j] 表示
s[i..j] 是否回文：
s[i] == s[j] 且（区间长 < 3 或
dp[i+1][j-1]）。
def longestPalindrome(s: str) -> str:
n = len(s)
dp = [[False] * n for _ in range(n)]
best_l, best_r = 0, 0
for i in range(n - 1, -1, -1):
for j in range(i, n):
dp[i][j] = s[i] == s[j] and (j - i < 2 or dp[i + 1][j - 1])
if dp[i][j] and j - i > best_r - best_l:
best_l, best_r = i, j
return s[best_l:best_r + 1]
时间同样是
O(n²)，但
空间 O(n²) —— 中心扩展
O(1)。DP 的价值是提供了另一个视角（大回文由小回文长出来），面试时口头对照即可，动手写中心扩展。
5.2 Manacher（O(n)，知道即可）
在字符间插
#（
"abba" →
"#a#b#b#a#"），奇偶回文统一成奇数长度，再用已算出的回文半径跳过重复比较，做到线性。
面试手写性价比低：状态多、易错，除非岗位明确要求线性算法，口头说"存在 Manacher，O(n)，思路是插分隔符统一奇偶 + 利用已算半径"就够了。
5.3 同族题
家族口诀：
"连续子串 → 枚举中心；不连续子序列 → 区间 DP" —— 分界线就是"能否由内部回文向外扩一格推出"。
六、Java 版
public String longestPalindrome(String s) {
int n = s.length(), bestL = 0, bestR = 0;
for (int i = 0; i < n; i++) {
int[] odd = expand(s, i, i); // 字符中心
if (odd[1] - odd[0] > bestR - bestL) { bestL = odd[0]; bestR = odd[1]; }
if (i + 1 < n && s.charAt(i) == s.charAt(i + 1)) {
int[] even = expand(s, i, i + 1); // 间隙中心
if (even[1] - even[0] > bestR - bestL) { bestL = even[0]; bestR = even[1]; }
}
}
return s.substring(bestL, bestR + 1);
}
private int[] expand(String s, int l, int r) {
while (l > 0 && r < s.length() - 1 && s.charAt(l - 1) == s.charAt(r + 1)) {
l--; r++;
}
return new int[]{l, r};
}
七、边界情况
八、复杂度
- 时间 O(n²)：
2n - 1 个中心，每个扩展最多 O(n)。
- 空间 O(1)：只有中心变量和最优边界 —— 比 DP 的
O(n²) 空间省一个量级，这也是它优于 DP 的实际理由。
九、常见坑
9.1 只写 expand(i, i)，漏掉偶数回文
最经典的 bug：
"cbbd" 会返回
"c"（长度 1），
"abba" 也一样。
中心必须交错枚举字符与间隙两类。自测方法：跑一遍
"cbbd"，答案必须是
"bb"。
9.2 扩展循环比较对象写错
while (s[l] == s[r]) 是"收缩式"写法 —— 初始
[i, i] 时
s[l] == s[r] 恒真，指针会走出字符串。扩展式写法比较的是
往外一格：
s[l-1] == s[r+1]，边界守卫
l > 0 && r < n - 1 恰好挡住越界。
9.3 同长度更新用 >= 导致结果漂移
>= 会让答案在多个等长回文间跳动（取决于枚举顺序），且最后一次更新不一定起点最靠左。用
> 先到先得，行为可预测。
9.4 间隙中心忘了先判相等
s[i] != s[i+1] 时还调用
expand(s, i, i+1) 不算错误（扩展循环自然不推进，返回
[i, i+1]），但这个"区间"
不是回文 —— 直接把它当候选更新答案就错了。先判
s[i] == s[i+1]，或把"是否真回文"的判断留给更新条件之外。
9.5 DP 边界差一位
dp[i][j] 的递推里
j - i < 2 兜底（长度 1、2 的区间不需要看内部）；写成
j - i <= 2 或漏掉都会把
"aa" 判成非回文。另外 DP 要
按 i 从大到小填，否则
dp[i+1][j-1] 还没算。
9.6 按 UTF-16 码元拆字符串
JS 里
s[i] /
s.split('') 按 UTF-16 码元切，emoji 会被拆成两个代理项，"同一个 emoji"互不相等、回文长度虚高。用
Array.from(s) 按码点拆（Python 天然按码点，无此问题）。
十、面试怎么答
- 一句话定性："回文由中心和半径决定，枚举
2n - 1 个中心向两边扩展 —— O(n²) 时间 O(1) 空间。"
- 主动报出 2n - 1："n 个字符中心管奇数回文，n - 1 个间隙中心管偶数回文 —— 漏间隙就漏
"abba"。"这句是面试官判断你真懂假懂的探针。
- 对照暴力：先说
O(n³) 的枚举子串账，再给出中心扩展怎么把"验证"融进"枚举"。
- 复杂度与对照：DP 同时间
O(n²) 空间；Manacher O(n) 但难写，口头提即可。
- 边界报菜名：
"cbbd"（偶数）、"aaaa"（连续相同）、"ac"（无回文退单字符）。
结语
最长回文子串的解法演进是一条"换视角"的路：枚举子串 → 枚举中心（少一个 n）→ 归一化中心 + 复用半径（Manacher，再少一个 n）。中心扩展是这条路上性价比最高的一站 —— 它的难点不在代码量，而在
2n-1 这个数字背后的奇偶两种中心。把间隙中心当成本题的肌肉记忆，同族的 LC 647 直接复用。