字符串

回文问题

回文题分三类，解法完全不同

「回文」这两个字下面藏着三种题，套错解法就会绕远路：

题型 解法 复杂度
判断一个串是不是回文 左右指针对撞 O(n)
找最长回文子串（连续） ⭐ 中心扩散 O(n²)
找最长回文子序列（可跳着取） 二维 DP O(n²)

🚨 子串和子序列差一个字，解法完全不同。 子串必须连续，所以能用「中心向外扩」； 子序列可以跳着取，中心扩散完全失效，只能上 DP。 读题时先确认是哪一个。

判断回文：左右指针

最简单的一类，就是左右指针对撞：

function isPalindrome(s) {
  let l = 0, r = s.length - 1;
  while (l < r) {
    if (s[l] !== s[r]) return false;
    l++; r--;
  }
  return true;
}

⭐ 循环条件是 l < r 而不是 l <= r：相等时是同一个字符，比它自己没有意义。

⚠️ 但这纯粹是省一次比较，不影响正确性 —— 5000 组随机串上两种写法结论完全一致。 而且多出来的那一次比较全部发生在「奇数长度且确实是回文」的串上（825/825 组）： 只有这时 l 和 r 才会正好撞在中间那个字符上。 📌 所以它是个洁癖级的优化，不是坑。真正的坑在下面那两节。

📌 变体「跳过非字母数字、忽略大小写」只是在两端加两个 while 跳过无效字符， 骨架不变。

最长回文子串：中心扩散

核心观察：每个回文串都有一个中心，从中心往两边扩，字符必然对称。 所以枚举所有可能的中心，各自尽量往外扩，取最长的那个。

function longestPalindrome(s) {
  let best = '';

  // 从 (l, r) 这个中心往两边扩，返回扩出来的最长回文
  const expand = (l, r) => {
    while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }
    return s.slice(l + 1, r);        // 🚨 退出时 l、r 都多走了一步
  };

  for (let i = 0; i < s.length; i++) {
    const odd = expand(i, i);        // 奇数长度：中心是一个字符
    const even = expand(i, i + 1);   // 🚨 偶数长度：中心是两个字符之间
    if (odd.length > best.length) best = odd;
    if (even.length > best.length) best = even;
  }
  return best;
}

🚨 「中心」有两种，漏掉一种三到四成的输入会出错

这是这题唯一的坑，而且它很会藏。

  • 奇数长度的回文（aba）中心是一个字符
  • 偶数长度的回文（abba）中心是两个字符之间的缝

只写 expand(i, i) 的话，所有偶数长度的回文都找不到。实测：

输入      正确答案   只试奇数中心
"babad"   "bab"      "bab"     ✅ 碰巧一样
"cbbd"    "bb"       "c"       ❌ 只剩单个字符
"abba"    "abba"     "a"       ❌
"aaaa"    "aaaa"     "aaa"     ❌ 少一个

⚠️ 注意第一行："babad" 这个最常见的示例上两种写法结果相同。 拿它自测完全测不出问题 —— 必须用偶数长度的回文（"cbbd"）才能暴露。

到底多久错一次

穷举长度 n、字母表大小 k 的全部串（不是抽样，与随机种子无关）， 统计只试奇数中心时答案长度错的比例：

k \ n     2      3      4      5      6      7      8      9     10
 2     50.0%  50.0%  37.5%  37.5%  46.9%  43.8%  42.2%  42.2%  42.0%
 3     33.3%  44.4%  40.7%  37.0%  36.6%  36.5%  36.9%  37.3%  37.7%
 4     25.0%  37.5%  39.1%  37.5%  35.8%  34.4%  33.6%  33.2%  33.1%

二元串继续往长了穷举：n=12 → 42.1%    n=14 → 42.0%    n=16 → 42.0%

⭐ 收敛到 三到四成，不是一半 —— 而且字母表越大越低（重复字符少，偶数回文就少）。 换句话说：六成左右的输入上这个错法碰巧是对的。

🚨 危险的正是这个比例。要是十成都错，写完第一次自测就发现了； 要是一成错，还能归到「边界没想清楚」。六成对、四成错是最难察觉的区间 —— 多测几组还是有大半是对的，容易得出「大方向没问题，只是某个边界没处理好」的错误结论。

📌 记法：中心有 2n-1 个（n 个字符 + n-1 条缝），不是 n 个。 ⚠️ 但代码里的循环跑了 2n 次 —— 最后一次 expand(n-1, n) 右边直接越界， 恒返回空串。它是空转，不影响正确性，只是别把它数成中心。

⚠️ expand 返回时的那个 +1

while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }
return s.slice(l + 1, r);

循环退出时，l 和 r 已经各自多走了一步（走到了不匹配或越界的位置）。 所以真正的回文区间是 [l+1, r-1]，而 slice(l+1, r) 正好取到这一段 （slice 右开）。

两种写错法的症状完全不同，别混为一谈。

s.slice(l + 1, r - 1) —— 干干净净的差一位。5000 组随机串里 5000 组都是「恰好短一个字符」，一次例外都没有。规律稳定，反而好查。

s.slice(l, r) —— 这个不是差一位，它会踩到 JavaScript 的负数索引。

🚨 l 扩到左边界时是 -1，而 s.slice(-1, r) 里的 -1 被解释成 「从末尾倒数第 1 个」，起点一下子跳到串尾：

"aa"    中心(0,1) 扩完 l=-1 r=2   slice(l+1,r)="aa"    slice(l,r)="a"    短了
"aaaa"  中心(0,1) 扩完 l=-1 r=2   slice(l+1,r)="aa"    slice(l,r)=""     空的
"cbbd"  中心(0,1) 扩完 l= 0 r=1   slice(l+1,r)=""      slice(l,r)="c"    长了

"aaaa" 那行最典型：slice(-1, 2) 的起点算出来是 3，终点是 2，起点在终点后面 —— 返回空串。而 l >= 0 时它又确实是「首尾各多一个不匹配字符」。 5000 组随机串的最终答案：

比正确答案长   2668 组 = 53.4%      （l >= 0，多含两个字符）
等长           1496 组 = 29.9%
比正确答案短    836 组 = 16.7%      （l = -1，负数索引截断）

⚠️ 而 l = -1 在 5000/5000 组随机串上都出现过 —— 只要串里有回文能扩到开头， 就会走到那个分支。所以这不是罕见路径，是每次都在发生。

⭐ 判据：slice 的下标可能算出负数时，它就不再是「差一位」那类 bug —— arr[-1] 只是 undefined，但 slice(-1, …) 会给你一个语义完全不同的结果。 症状忽长忽短没规律，正是这个原因。

三种解法怎么选

中心扩散 O(n²) 时间、O(1) 空间，代码十来行。

DP 也能做最长回文子串（dp[i][j] = s[i..j] 是不是回文）， 同样 O(n²) 时间，但要 O(n²) 空间。

⭐ 所以求最长回文子串，中心扩散完胜 DP。但「完胜」在哪，实测下来和直觉不一样。 数两者各走了多少步（数步数而不是计时，可复现、不受 JIT 干扰）：

随机串（abcd 四个字母）
  长度      扩散步数      DP 步数     DP / 扩散
   100          373         5050        13.5×
   400         1489        80200        53.9×
  1600         5944      1280800       215.5×

全同字符串 "aaa…"（扩散的最坏情况）
   100         5250         5050         1.0×
   400        81000        80200         1.0×
  1600      1284000      1280800         1.0×

🚨 「同样的时间」严重低估了扩散。 随机输入上它根本跑不满 O(n²) —— n=1600 只走了 5944 步，约 3.7n，接近线性。因为随机串里几乎没有长回文， 每个中心扩一两步就撞上不匹配退出了。而 DP 无论输入长什么样都必须填满 n² 个格子。

⭐ 两者真正打平只在全同字符串这种极端输入上（1.0×）—— 那时每个中心都能一路扩到底，扩散才吃满 O(n²)。

⚠️ 而「代码更短」这条几乎不成立：本篇的中心扩散版 14 行， 一份等价的干净 DP 版 15 行，只差一行。真正硬的差距是空间： 扩散 0 个额外格子，DP 要 n² 个（n=1600 就是 256 万个）。 👉 要挑一条理由记住，记「空间」，别记「代码短」。

DP 在这题上唯一的价值是「顺便得到所有子串的回文性」， 而那个信息在「分割回文串」这类题里才用得上。

📌 还有个 O(n) 的 Manacher 算法。面试里出现频率极低， 知道「有这么个东西、能做到线性」就够 —— 现场手写它的收益远低于把中心扩散写利索。

与子序列题的分界

再强调一次这两者的差别，因为它决定了整个解法：

s = "bbbab"
  最长回文【子串】   → "bbb"   （连续）
  最长回文【子序列】 → "bbbb"  （跳过中间的 a）

⭐ 子序列的答案可以更长，因为它允许跳。而「允许跳」意味着没有固定中心， 中心扩散无从下手 —— 那题的状态是 dp[i][j] = s[i..j] 里最长回文子序列的长度， 属于子序列类型问题那一章的模板。

本章到此为止

字符串三篇讲完了：JS 的坑、 KMP、回文。

⭐ 回头看，字符串题真正「字符串特有」的只有 KMP 和回文两块 —— 其余的（去重、滑窗、双指针、DP）都是把数组那套技巧原样搬过来。 所以卡住的时候，先问一句：这题去掉「字符串」这层皮，是道什么题？

练习

勾选记录做过哪些，0 / 5 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。

在本站 OJ 上练

这几道题在自己搭的判题机上，注册后直接提交，几秒出结果 —— 不用装环境、不用自己造测试数据。题目是自出的（无版权问题），每道题的数据都要求能抓出典型错解才准上线， 所以「样例过了」不等于能过。