如何求最长回文子串？（中心扩展法，LeetCode 5）

简化版

求字符串 s 中最长的回文子串（正读反读相同的连续子串）。最实用的中心扩展法：回文串以「中心」对称，遍历每个可能的中心，向两边扩展直到字符不相等，记录最长的。中心有 2n-1 个——n 个单字符中心（奇数长度回文）和 n-1 个字符间隙中心（偶数长度回文）。每个中心扩展 O(n)，总 O(n²) 时间、O(1) 空间。追求 O(n) 可用 Manacher 算法。

详细版

String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    int start = 0, end = 0;           // 最长回文的边界
    for (int i = 0; i < s.length(); i++) {
        int len1 = expand(s, i, i);       // 奇数长度：以 i 为中心
        int len2 = expand(s, i, i + 1);   // 偶数长度：以 i、i+1 间隙为中心
        int len = Math.max(len1, len2);
        if (len > end - start + 1) {
            start = i - (len - 1) / 2;    // 由中心和长度反推左边界
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

// 从中心 [left, right] 向两边扩展，返回回文长度
int expand(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--; right++;
    }
    return right - left - 1;          // 退出时多走了一步，长度是 right-left-1
}

中心扩展：枚举每个中心，向两侧扩展找以它为中心的最长回文。
两类中心：单字符（奇回文）和字符间隙（偶回文），共 2n-1 个。
复杂度：O(n²) 时间、O(1) 空间。Manacher 可达 O(n)。

完整版教学

一、回文的对称性：从中心想起

回文串「正读反读相同」，本质是关于中心对称。"aba" 关于中间的 b 对称，"abba" 关于中间两个 b 的间隙对称。所以找回文的自然思路是：固定一个对称中心，向左右同时扩展，只要两边字符相等就继续扩，直到不等——扩出来的就是以该中心的最长回文。

二、两类中心：奇数与偶数长度

回文长度有奇有偶，对称中心也分两类：

奇数长度回文（如 "aba"）：中心是一个字符（b）。以每个字符 s[i] 为中心扩展，expand(i, i)。
偶数长度回文（如 "abba"）：中心是两个字符之间的间隙（两个 b 中间）。以每对相邻字符 s[i], s[i+1] 为中心扩展，expand(i, i+1)。

所以对每个 i 都要试这两种中心，共 2n-1 个中心（n 个单字符 + n-1 个间隙）。取所有中心扩出的回文里最长的。

三、扩展函数的细节

expand(left, right) 从中心向两边走：只要 left >= 0 && right < n && s[left] == s[right] 就 left--、right++ 继续扩。退出循环时，left 和 right 已经各多走了一步（指向不相等或越界的位置），所以真正的回文是 [left+1, right-1]，长度为 right - left - 1。这个「多走一步」的边界很容易算错，记住长度 = right - left - 1。

由中心 i 和回文长度 len 反推左右边界：start = i - (len-1)/2、end = i + len/2（对奇偶都成立，可背）。

四、复杂度与 Manacher

中心扩展 O(n²)：2n-1 个中心，每个最多扩 O(n)。空间 O(1)。这是面试的标准答案，简洁够用。
动态规划 O(n²)：dp[i][j] 表示 s[i..j] 是否回文，dp[i][j] = (s[i]==s[j]) && dp[i+1][j-1]。时间同，但要 O(n²) 空间，一般不如中心扩展。
Manacher 算法 O(n)：通过「插入分隔符统一奇偶 + 利用回文的对称性复用已算信息（维护最右回文边界和中心）」把复杂度降到线性。原理较复杂，属加分项，能说出「Manacher 可做到 O(n)」即可。

五、易错点

忘了偶数中心：只写 expand(i, i) 会漏掉 "abba" 这类偶回文。必须两种都试。
长度计算：expand 返回 right - left - 1（退出时多走一步），不是 right - left。
边界反推：start = i - (len-1)/2 用整除，奇偶都对，别手推错。
空串/单字符：单字符本身是长度 1 的回文，代码天然处理；空串返回 ""。

六、每个回文都有唯一的中心表示

长度为奇数的回文中心是一个字符，长度为偶数的回文中心是两个字符之间的缝。枚举 n 个单字符中心和 n-1 个缝中心，就覆盖所有 2n-1 种可能；从中心向两侧扩展直到失配，得到该中心能产生的最长回文。

s="babad"
中心 (1,1) 字符 a：a -> bab，长度 3
继续比较 s[-1] 与 s[3]，越界停止
中心 (2,2) 字符 b：b -> aba，长度 3
偶数中心 (1,2)：a != b，长度 0
可返回 "bab" 或 "aba"
题目通常接受任一最长答案

校验维度	本题必须保持的结论
循环/递推不变量	扩展循环内 `[left+1,right-1]` 已是回文；两端相等时扩成更大回文。
边界条件	更新答案时真实区间是扩展停止后的 `[left+1,right-1]`；空串需按接口约定处理。
复杂度与代价	中心扩展最坏 O(n²) 时间、O(1) 额外空间；Manacher 可做到 O(n)。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

字符串题首先要固定“处理的是字符、UTF-16 代码单元还是 Unicode 码点”，再讨论下标与窗口。本题应先复述这条不变量：扩展循环内 [left+1,right-1] 已是回文；两端相等时扩成更大回文。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“s=“babad””开始手推，最后应得到“题目通常接受任一最长答案”。
边界复核：更新答案时真实区间是扩展停止后的 [left+1,right-1]；空串需按接口约定处理。
代价复核：中心扩展最坏 O(n²) 时间、O(1) 额外空间；Manacher 可做到 O(n)。
用空串、单字符、全相同字符和首尾命中检查下标边界。
涉及窗口或双指针时，明确区间是闭区间还是左闭右开，并在移动后再判断长度。
涉及计数数组时，先确认题目字符集；超出小写英文字母就不能硬套 26 个桶。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“扩展循环内 [left+1,right-1] 已是回文；两端相等时扩成更大回文。”这条正确性主线不能省。

八、常见误区与追问

误区：只枚举字符中心即可。 会漏掉 abba 这类偶数长度回文，必须同时枚举缝中心。
误区：最长回文子串与最长回文子序列相同。 子串要求连续；子序列可跳过字符，通常用不同的动态规划。
误区：中心扩展的最坏时间是 O(n)。 像全相同字符时，每个中心都扩展很远，总计 O(n²)。
追问：两个同长答案如何处理？ 若题目允许任一答案，使用 > 或 >= 只会影响保留先后，不影响正确性。
追问：DP 解法的状态是什么？ dp[l][r] 表示闭区间是否回文，依赖字符相等且内部区间回文。
追问：Manacher 为什么能线性？ 它利用已知最右回文边界的镜像半径，避免重复扩展已覆盖区域。

九、加强记忆

最长回文子串 = 中心扩展法：回文关于中心对称，枚举 2n-1 个中心（n 个单字符中心=奇回文、n-1 个字符间隙中心=偶回文），每个中心 expand(left,right) 向两边扩到字符不等，回文长度 = right-left-1（退出多走一步）。O(n²) 时间 O(1) 空间。务必同时试 expand(i,i) 和 expand(i,i+1)（别漏偶回文）。追求 O(n) 用 Manacher（插分隔符统一奇偶 + 复用对称信息）。核心：从每个中心往两边撑，撑不动为止。

简化版

详细版