区间动态规划例题：最小插入次数构造回文串问题（相邻字符交换允许）

题目描述

给定一个字符串s，你可以进行两种操作：

1. 在任意位置插入任意字符（成本为1）
2. 交换任意两个相邻字符（成本为0，即免费）

请问至少需要多少次插入操作（交换操作免费不计入成本），才能将原字符串变成回文串？

解题思路

这个问题是经典的最小插入次数构造回文串问题的变种。由于交换操作免费，我们可以重新排列字符串中的字符，这大大增加了问题的灵活性。

关键观察点：

• 交换免费意味着我们可以任意重新排列字符
• 最终目标是形成回文串，需要满足字符的对称性
• 问题等价于：找到原字符串中最长的子序列，使得该子序列可以排列成回文串
• 最小插入次数 = 字符串总长度 - 最长可排列成回文串的子序列长度

详细解题过程

步骤1：问题分析
由于交换操作免费，我们可以任意重新排列字符。回文串的特点是：最多有一个字符出现奇数次，其他字符都出现偶数次。

因此，问题转化为：从原字符串中选择字符，组成一个回文串，使得选择的字符数最大化。最小插入次数就是总长度减去这个最大字符数。

步骤2：动态规划状态定义
定义dp[i][j]表示子串s[i...j]中最长的可以排列成回文串的子序列长度。

步骤3：状态转移方程

情况1：如果s[i] == s[j]

• 当i == j时：dp[i][j] = 1（单个字符本身就是回文）
• 当i + 1 == j时：dp[i][j] = 2（两个相同字符可以组成回文）
• 其他情况：dp[i][j] = dp[i+1][j-1] + 2
  （两端的相同字符可以加入到回文序列中）

情况2：如果s[i] != s[j]

• dp[i][j] = max(dp[i+1][j], dp[i][j-1])
  （选择去掉左端或右端字符的较优解）

步骤4：边界条件

• 当i > j时：dp[i][j] = 0（空子串）
• 当i == j时：dp[i][j] = 1（单个字符）

步骤5：计算顺序
按子串长度从小到大计算：

1. 长度为1的子串
2. 长度为2的子串
3. 长度为3的子串
   ...
   n. 长度为n的子串（整个字符串）

步骤6：结果计算
最小插入次数 = n - dp[0][n-1]
其中n是原字符串长度。

举例说明

例1：s = "abca"

• 最长可排列成回文串的子序列："aba"或"aca"，长度3
• 最小插入次数：4 - 3 = 1

例2：s = "abcde"

• 最长可排列成回文串的子序列：任意单个字符，长度1
• 最小插入次数：5 - 1 = 4

算法实现

def min_insertions_with_free_swaps(s):
    n = len(s)
    if n == 0:
        return 0
    
    dp = [[0] * n for _ in range(n)]
    
    # 初始化：单个字符
    for i in range(n):
        dp[i][i] = 1
    
    # 按子串长度从小到大计算
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            if s[i] == s[j]:
                if length == 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])
    
    return n - dp[0][n - 1]

# 测试示例
print(min_insertions_with_free_swaps("abca"))  # 输出：1
print(min_insertions_with_free_swaps("abcde")) # 输出：4

时间复杂度分析

• 时间复杂度：O(n²)，需要填充n×n的DP表
• 空间复杂度：O(n²)，用于存储DP表

这个算法通过动态规划高效地解决了问题，充分利用了免费交换操作带来的灵活性。