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

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

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

问最少需要多少次插入（交换操作免费），才能将字符串变成回文串。

解题思路
这个问题是经典的回文串构造问题的变种，由于允许免费交换相邻字符，我们可以重新排列字符串中的字符。关键思路是：

• 免费交换意味着我们可以以任意顺序排列字符
• 问题转化为：通过最少插入使字符串能排列成回文串
• 回文串的条件：最多一个字符出现奇数次，其他都出现偶数次

详细解题步骤

步骤1：问题分析
由于交换免费，我们只需关心每个字符的出现次数，而不关心它们的相对位置。
对于一个回文串：

• 如果字符串长度是偶数：所有字符都必须出现偶数次
• 如果字符串长度是奇数：恰好一个字符出现奇数次，其他都出现偶数次

步骤2：统计字符频率
首先统计字符串中每个字符的出现频率：

from collections import Counter
def min_insertions(s):
    freq = Counter(s)

步骤3：计算需要调整的字符
我们需要确保最多只有一个字符出现奇数次。
对于出现奇数次的字符，我们只能保留其中一个（如果字符串长度是奇数），其他的都需要调整。

计算出现奇数次的字符数量：

odd_count = sum(1 for count in freq.values() if count % 2 == 1)

步骤4：确定最小插入次数
如果odd_count <= 1，那么字符串已经可以通过重新排列变成回文串，不需要插入，答案为0。

如果odd_count > 1，我们需要通过插入操作来减少奇数个数的字符。
每个插入操作可以：

• 要么将一个出现奇数次的字符变成出现偶数次
• 要么减少奇数个数的字符数量

实际上，最小插入次数是max(0, odd_count - 1)：

return max(0, odd_count - 1)

步骤5：完整算法实现

from collections import Counter

def min_insertions_to_palindrome(s):
    """
    计算将字符串通过插入和免费交换变成回文串的最小插入次数
    
    参数:
        s: 输入字符串
        
    返回:
        最小插入次数
    """
    # 统计字符频率
    freq = Counter(s)
    
    # 计算出现奇数次的字符个数
    odd_count = 0
    for count in freq.values():
        if count % 2 == 1:
            odd_count += 1
    
    # 最小插入次数为 max(0, 出现奇数次的字符数 - 1)
    return max(0, odd_count - 1)

步骤6：示例验证

例1：s = "aabb"

• 频率：{'a':2, 'b':2}，都是偶数
• odd_count = 0
• 结果：0（已经是回文"abba"）

例2：s = "abc"

• 频率：{'a':1, 'b':1, 'c':1}，都是奇数
• odd_count = 3
• 结果：2（可以插入2个字符，如"abcba"）

例3：s = "aab"

• 频率：{'a':2, 'b':1}，一个奇数
• odd_count = 1
• 结果：0（可以重排为"aba"）

步骤7：算法正确性证明

• 如果odd_count ≤ 1，字符串已经满足回文条件
• 如果odd_count > 1，我们需要将多余的奇数个字符通过插入操作配对
• 每个插入操作可以减少一个奇数个字符
• 最终只需要保留一个奇数个字符（如果总长度为奇数）或0个（如果总长度为偶数）

步骤8：时间复杂度分析

• 统计频率：O(n)，其中n是字符串长度
• 计算奇数个数：O(k)，其中k是字符集大小
• 总时间复杂度：O(n)，非常高效

这个解法利用了免费交换的特性，将复杂的位置调整问题简化为简单的频率统计问题。