最长回文子序列的最少插入次数

题目描述

给你一个字符串 s，你可以向字符串的任意位置（包括开头和末尾）插入任意字符，目标是使最终得到的字符串成为一个回文串。请计算最少需要插入多少个字符。

示例 1
输入：s = "zzazz"
输出：0
解释：原字符串本身就是回文串，无需插入。

示例 2
输入：s = "mbadm"
输出：2
解释：可以在开头插入"m"，末尾插入"m"，得到"mbdadbm"；或者插入其他字符构成回文，但最少需要2次插入。

示例 3
输入：s = "leetcode"
输出：5
解释：插入5个字符可以构成回文串，例如"leetcodocteel"。

约束条件

• 字符串长度 n 满足 1 ≤ n ≤ 500
• 字符串仅由小写英文字母组成

解题思路

这个问题本质上是最长回文子序列（LPS）的一个变种。我们先分析一下核心思路：

1. 问题转换
   对于一个字符串，如果我们能找到它的最长回文子序列（不需要连续），那么那些不在这个子序列中的字符，都需要通过插入对应的字符来匹配，从而形成完整的回文串。

2. 关键观察
   设字符串长度为 n，其最长回文子序列长度为 lps。
   那么不在最长回文子序列中的字符有 n - lps 个。
   对于每个这样的字符，我们都需要插入一个对应的字符来配对。
   因此，最少插入次数 = n - lps

3. 问题转化
   原问题等价于：求字符串的最长回文子序列的长度。
   然后计算 n - lps 即可。

详细解题步骤

步骤1：定义状态

我们定义 dp[i][j] 表示字符串 s 从位置 i 到位置 j（包含两端）的子串中，最长回文子序列的长度。

其中 0 ≤ i ≤ j < n，n 是字符串长度。

步骤2：状态转移方程

我们需要分情况讨论：

1. 基础情况：当子串长度为1时，即 i == j
   此时子串本身就是回文，所以：

   dp[i][i] = 1
   

2. 当 s[i] == s[j] 时
   如果两端的字符相等，那么它们可以成为回文子序列的两端。
   我们需要加上中间子串的最长回文子序列长度：

   dp[i][j] = dp[i+1][j-1] + 2
   

   注意：当 j = i+1 时，dp[i+1][j-1] 表示空串，长度为0。

3. 当 s[i] != s[j] 时
   两端的字符不能同时作为回文子序列的两端。我们有两种选择：

   • 舍弃左端字符 s[i]，考虑子串 s[i+1..j]
   • 舍弃右端字符 s[j]，考虑子串 s[i..j-1]

   取两者的最大值：

   dp[i][j] = max(dp[i+1][j], dp[i][j-1])
   

步骤3：计算顺序

由于 dp[i][j] 依赖于 dp[i+1][j-1]、dp[i+1][j] 和 dp[i][j-1]，我们需要按子串长度从小到大的顺序计算：

1. 先计算所有长度为1的子串（i == j）
2. 然后计算长度为2的子串
3. 依次增加长度，直到计算整个字符串

步骤4：边界条件

• 当 i > j 时，表示空串，长度为0
• 当 i == j 时，长度为1

步骤5：最终答案

计算完整个字符串的 dp[0][n-1] 后，最少插入次数为：

最少插入次数 = n - dp[0][n-1]

示例推导

让我们以 s = "mbadm" 为例（n=5）：

初始化：

dp[0][0] = 1  // "m"
dp[1][1] = 1  // "b"
dp[2][2] = 1  // "a"
dp[3][3] = 1  // "d"
dp[4][4] = 1  // "m"

长度=2的子串：

• i=0, j=1: s[0]="m", s[1]="b" 不相等
  dp[0][1] = max(dp[1][1], dp[0][0]) = max(1,1) = 1
• i=1, j=2: "b"≠"a"
  dp[1][2] = max(dp[2][2], dp[1][1]) = 1
• i=2, j=3: "a"≠"d"
  dp[2][3] = 1
• i=3, j=4: "d"≠"m"
  dp[3][4] = 1

长度=3的子串：

• i=0, j=2: s[0]="m", s[2]="a" 不相等
  dp[0][2] = max(dp[1][2], dp[0][1]) = max(1,1) = 1
• i=1, j=3: "b"≠"d"
  dp[1][3] = max(dp[2][3], dp[1][2]) = 1
• i=2, j=4: "a"≠"m"
  dp[2][4] = max(dp[3][4], dp[2][3]) = 1

长度=4的子串：

• i=0, j=3: "m"≠"d"
  dp[0][3] = max(dp[1][3], dp[0][2]) = 1
• i=1, j=4: "b"≠"m"
  dp[1][4] = max(dp[2][4], dp[1][3]) = 1

长度=5的子串（整个字符串）：

• i=0, j=4: s[0]="m", s[4]="m" 相等
  dp[0][4] = dp[1][3] + 2 = 1 + 2 = 3

最长回文子序列长度 = dp[0][4] = 3
最少插入次数 = 5 - 3 = 2

验证：最长回文子序列可以是 "mam" 或 "mbm"，长度都是3。需要插入2个字符构成完整回文，如 "mbdadbm"。

代码实现（Python）

def minInsertions(s: str) -> int:
    n = len(s)
    if n <= 1:
        return 0
    
    # 初始化dp数组
    dp = [[0] * n for _ in range(n)]
    
    # 基础情况：长度为1的子串
    for i in range(n):
        dp[i][i] = 1
    
    # 按子串长度从小到大计算
    for length in range(2, n + 1):  # 子串长度从2到n
        for i in range(n - length + 1):
            j = i + length - 1
            
            if s[i] == s[j]:
                if length == 2:
                    # 长度为2且两端相等
                    dp[i][j] = 2
                else:
                    dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    
    lps_length = dp[0][n-1]
    return n - lps_length

复杂度分析

• 时间复杂度：O(n²)，需要填充 n × n 的dp表
• 空间复杂度：O(n²)，存储整个dp表

空间优化

注意到 dp[i][j] 只依赖于 dp[i+1][j-1]、dp[i+1][j] 和 dp[i][j-1]，我们可以优化空间到 O(n)：

def minInsertions_optimized(s: str) -> int:
    n = len(s)
    if n <= 1:
        return 0
    
    # 使用一维数组
    dp = [0] * n
    
    for i in range(n-1, -1, -1):
        prev = 0  # 保存dp[i+1][j-1]
        dp[i] = 1
        for j in range(i+1, n):
            temp = dp[j]  # 保存当前的dp[j]，下一轮作为prev
            
            if s[i] == s[j]:
                dp[j] = prev + 2
            else:
                dp[j] = max(dp[j], dp[j-1])
            
            prev = temp
    
    lps_length = dp[n-1]
    return n - lps_length

思考扩展

1. 如果不仅允许插入，还允许删除字符，最少操作次数是多少？（这就是编辑距离问题的回文版本）
2. 如果要求输出具体的插入方案，如何修改算法？
3. 如果字符串长度很大（比如10^4），如何进一步优化？

这个问题的核心在于理解：使字符串变成回文的最少插入次数 = 字符串长度 - 最长回文子序列长度。一旦理解了这个关系，问题就转化为了经典的最长回文子序列问题。