笔试真题复盘：删掉最少的字符，把串变成最长回文

图 1：答案藏在上三角表的最右上角。

先说明属性：这是一篇历史笔试题复盘，题目出自本地笔试题集资料，与任何公司的当前招聘无关。这道题的第一层陷阱不在算法，而在题意转换——很多人读完题就开始枚举删除方案，方向从一开始就错了。

第一步：把「最少删除」翻译成「最长保留」。

题目要求：给定字符串 s，可以删一些字符，让剩下的串是回文，输出最少要删几个。枚举删除方案是指数级的，走不通。换个角度看：删得最少，等价于留下的回文最长。所以答案就是 n 减去「最长回文子序列」的长度，问题瞬间变成经典 DP。

这里必须咬死一个概念：子序列不等于子串。子串要求连续，子序列只要求相对顺序不变，中间可以跳格。「bbbab」的最长回文子序列是「bbbb」——跳过那个 a，四个 b 隔着位置照样算数。正因为允许跳格，中心扩展、Manacher 这些为连续子串设计的武器全部失效，这类题的唯一正解是区间 DP。

第二步：设计区间 DP 的状态与转移。

定义 dp[i][j] 为子串 s[i..j] 内最长回文子序列的长度。转移只看区间两端：

• 两端相等，s[i] == s[j]：这对字符可以同时收进回文，dp[i][j] = dp[i+1][j-1] + 2；
• 两端不等：至少有一端用不上，舍弃较亏的一端，dp[i][j] = max(dp[i+1][j], dp[i][j-1])。

边界是对角线：单字符区间 dp[i][i] = 1，任何单字符本身就是回文。注意每个格子只依赖左、下、左下三个更短的区间，所以填表必须按区间长度从小到大递推——先填所有长度 2 的格子，再填长度 3、4，直到填出右上角 dp[0][n-1]。拿「bbbab」走一遍：长度 2 的区间里「bb」填 2、「ba」「ab」填 1；逐层向上，「bbba」两端不等取 max 得 3，最终 dp[0][4] = 4，答案 5 - 4 = 1，删掉唯一的 a 即可。

第三步：代码实测。

下面用 Node.js 22.15.0 运行（node lps.js），除了例题再补几个串验证边界：

function minDeletionsToPalindrome(s) {
  const n = s.length;
  // dp[i][j] = 子串 s[i..j] 的最长回文子序列长度
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let i = 0; i < n; i++) dp[i][i] = 1;            // 单字符必为回文
  for (let len = 2; len <= n; len++) {                 // 按区间长度递推
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      if (s[i] === s[j]) {
        dp[i][j] = dp[i + 1][j - 1] + 2;               // 两端收入回文
      } else {
        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); // 舍弃一端
      }
    }
  }
  return { lps: dp[0][n - 1], del: n - dp[0][n - 1] };
}
for (const s of ["bbbab", "abca", "racecar", "aebcbda"]) {
  const r = minDeletionsToPalindrome(s);
  console.log(`${s}: 最长回文子序列长 ${r.lps}, 最少删除 ${r.del}`);
}

实测输出：

bbbab: 最长回文子序列长 4, 最少删除 1
abca: 最长回文子序列长 3, 最少删除 1
racecar: 最长回文子序列长 7, 最少删除 0
aebcbda: 最长回文子序列长 5, 最少删除 2

「bbbab」与手工填表一致；「racecar」本身已是回文，删 0 个；「aebcbda」最长回文子序列是「abcba」，删 2 个。一个小细节：长度 2 且两端相等时会读 dp[i+1][i]，这是「空区间」位置，初始化为 0 正好天然正确，不需要特判。

图 2：按区间长度递推，每个格子只看左、下、左下。

收尾的复杂度与优化空间。

时间 O(n²)、空间 O(n²)：格子数约 n²/2，每格 O(1)。空间可以优化——转移只用长度 len-1 和 len-2 两层，滚动数组能压到 O(n)，但笔试场上先把 O(n²) 写对远比炫技重要。同一个状态定义还能顺手解出另一道常见变体「最少插入几次让串变回文」，答案同样是 n - dp[0][n-1]，删除和插入在这道题里是对称的。

笔试答题的建议顺序：先一句话完成题意转换（最少删除 = n - 最长回文子序列），再声明子序列不连续所以用区间 DP，给出状态定义和两条转移，最后补复杂度。面试官如果追问「为什么不用中心扩展」，标准回答是：中心扩展枚举的是连续回文子串，而这题允许跳格，两者解的不是同一个问题。你第一次做这题时有没有把子序列当成子串？后来是怎么发现自己想岔了的？欢迎说说。