解题思路 - 5 最长回文子串

5. 最长回文子串（原题卡片见 GRD 字符串）

考点归类

字符串（String）· 双指针中心扩散法（Center Expansion） · 区间型动态规划（Interval DP）。大厂前端面试高频考察题（CodeTop 前端岗 Top 20）。

动机先行与形式化定义

• 现实场景：生物信息学中的 DNA 发夹结构对称匹配、编译原理中的对称语法单元解析。
• 输入：字符串 s（$1\le s.length\le 1000$）。
• 输出：s 中长度最长的回文连续子串。
• 复杂度瓶颈：朴素暴力枚举所有子串需要 $O(n^2)$，验证回文需 $O(n)$，整体是 $O(n^3)$。必须消除验证过程中的重复字符比较。

---

核心突破：从「对撞」到「外扩」

在 GRD 字符串 的 125 题（验证回文串）中，我们使用双指针对撞法（从两端向中间收缩）。而在寻找最长回文子串时，逆向思维是以某个中心向两端外扩：

1. 奇数对称中心：以单个字符为中心（如 "aba" 的 'b'），两边各扩散扩展。初始化 left = i, right = i。
2. 偶数对称中心：以两个相邻字符间隙为中心（如 "abba" 的两个 'b'），向两边扩展。初始化 left = i, right = i + 1。
3. 中心数量：长度为 $n$ 的字符串，共有 $n$ 个单字符中心和 $n-1$ 个双字符中心，合计 $2n-1$ 个中心。对每个中心单次扩展最多走 $O(n)$，总时间复杂度降至 $O(n^2)$，且额外空间仅需 $O(1)$。

---

避坑辨析：结算时机与边界公式

在编写中心扩散辅助函数时，主要有两种结算时机：

写法 A：实时结算法（心智负担极低，推荐）

在 while 内部、指针尚未移动前结算。因为刚通过 s[i] === s[j] 验证，当前闭区间 [i, j] 必定是合法回文，长度直接使用自然的 j - i + 1，无需任何修正计算：

while (i >= 0 && j < s.length && s[i] === s[j]) {
    let len = j - i + 1;
    if (len > maxLen) {
        maxLen = len;
        start = i; // 只记录坐标，避免每步频繁 s.slice() 产生 GC 压力
    }
    i--;
    j++;
}

写法 B：事后倒退法（跳出循环后结算）

让指针一直向外走直到越界或失配退出。跳出时 i 和 j 已经各自多跨了一步无效位置，合法区间为 [i + 1, j - 1]：

• 合法长度：$(j-1)-(i+1)+1=\mathbf{j}-\mathbf{i}-1$
• 合法起始：$\mathbf{i}+1$

---

完整解法实现

解法一：双指针中心扩散法（最优工程解）

/**
 * 5. 最长回文子串（双指针中心扩散 - 实时结算与索引优化版）
 * 时间复杂度: O(n^2) - 最多 2n-1 个中心，每个中心最坏扩散 O(n)
 * 空间复杂度: O(1) - 全程只维护数字坐标，仅在最后 return 时 slice 一次
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if (s.length < 2) return s;
 
    let start = 0;
    let maxLen = 1;
 
    // 辅助函数：以 i, j 为初始中心向外扩展
    const expand = (i, j) => {
        // 短路保护：必须先检查索引边界，再比较字符，防止 undefined === undefined 陷阱
        while (i >= 0 && j < s.length && s[i] === s[j]) {
            const curLen = j - i + 1;
            if (curLen > maxLen) {
                maxLen = curLen;
                start = i; // 记录最长子串的起始位置
            }
            i--;
            j++;
        }
    };
 
    // 遍历每一个可能的对称中心
    for (let i = 0; i < s.length; i++) {
        expand(i, i);     // 奇数长度中心（如 "aba"）
        expand(i, i + 1); // 偶数长度中心（如 "abba"）
    }
 
    return s.slice(start, start + maxLen);
};

解法二：区间动态规划（DP）

定义二维数组 dp[i][j] 表示子串 s[i...j] 是否为回文串：

• 状态转移方程：$dp[i][j]=(s[i]==s[j])\wedge (j-i<3\vee dp[i+1][j-1])$
• 遍历顺序：因依赖左下方的 dp[i + 1][j - 1]，必须按子串长度 $L$ 自小到大递增遍历，或从下到上倒序遍历 $i$。

/**
 * 5. 最长回文子串（区间动态规划）
 * 时间复杂度: O(n^2)
 * 空间复杂度: O(n^2) - 需维护 n x n 的状态矩阵
 * @param {string} s
 * @return {string}
 */
var longestPalindromeDP = function(s) {
    const n = s.length;
    if (n < 2) return s;
 
    let start = 0, maxLen = 1;
    const dp = Array.from({ length: n }, () => new Array(n).fill(false));
 
    // 单个字符必然是回文
    for (let i = 0; i < n; i++) {
        dp[i][i] = true;
    }
 
    // l 为子串长度，从 2 到 n
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1; // 右边界
 
            if (s[i] === s[j]) {
                if (len <= 3) {
                    dp[i][j] = true; // "aa" 或 "aba" 直接成立
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }
            } else {
                dp[i][j] = false;
            }
 
            if (dp[i][j] && len > maxLen) {
                maxLen = len;
                start = i;
            }
        }
    }
 
    return s.slice(start, start + maxLen);
};

---

解法对比表

解法	时间复杂度	空间复杂度	优劣分析
双指针中心扩散（推荐）	$O(n^2)$	$O(1)$	面试最优解。代码短小精悍，内存占用零分配，实际运行常数极佳。
区间动态规划（DP）	$O(n^2)$	$O(n^2)$	适合用来建立区间 DP 的子结构认知，但额外申请大数组容易触发内存限制。
Manacher（马拉车算法）	$O(n)$	$O(n)$	竞赛级算法，面试现场不要求手撕，若能口述“利用已知回文臂长镜像跳跃”属于加分项。

---

易错点与小抄

1. JS 越界判定：while 条件中必须确保 i >= 0 && j < s.length 写在 s[i] === s[j] 之前。若越界会返回 undefined，两边越界时 undefined === undefined 为 true 会导致死循环！
2. 切片时机优化：不要在扩散循环内部频繁调用 s.slice()，V8 引擎会在每次切片时在堆中新建字符串；改为记录 start 和 maxLen，最后只切一次。
3. 速记口诀：

   奇偶中心向外扩，边界相等进循环； 实时结账记首长，最后切片零负担。