修改字符串使无回文子串的最小修改次数

题目描述

给定一个只包含小写字母的字符串 s，每次操作可以将任意一个字符修改为任意其他小写字母。求最少需要多少次修改，使得修改后的字符串中不包含任何长度 ≥ 2 的回文子串。

回文子串：正着读和反着读相同的连续子串。

数据范围：1 <= s.length <= 10^5，s 仅由小写字母组成。

示例

示例 1：

输入： s = "ababa"
输出： 1
解释： 将第三个字符 'a' 修改为 'c'，得到 "abcba"，其中不含任何长度 ≥ 2 的回文子串。

示例 2：

输入： s = "aaaa"
输出： 2
解释： 一种修改方案："aaaa" → "abca"，共修改 2 次。

示例 3：

输入： s = "abc"
输出： 0
解释： 原字符串已经满足条件。

核心思路

关键观察

一个字符串不含长度 ≥ 2 的回文子串，当且仅当它同时满足：

1. 没有相邻相同字符（否则出现长度 2 的回文，如 "aa"）；
2. 没有间隔一个的相同字符（否则出现长度 3 的回文，如 "aba"）。

为什么？

• 任何长度 ≥ 4 的回文，其中心一定包含一个长度 2 或长度 3 的回文。
  • 例如 "abba" 中心是 "bb"（长度 2）；
  • "abcba" 中心是 "bcb"（长度 3）。
• 因此，只要消除了所有长度 2 和长度 3 的回文，就不会有更长的回文。

所以条件简化为：对每个位置 i（从 0 开始），

• 若 i >= 1，则 s[i] != s[i-1]；
• 若 i >= 2，则 s[i] != s[i-2]。

贪心策略

从左到右遍历字符串，对于每个位置 i：

• 如果 s[i] 与 s[i-1] 或 s[i-2] 相等，则必须修改 s[i]；
• 修改时，选择一个与 s[i-1] 和 s[i-2] 都不同的字符（因为字母表有 26 个字母，总能找到）；
• 修改后，继续处理后面的字符。

为什么贪心最优？

• 每个冲突是独立的：修改当前字符只会影响它后面的字符，不会影响已经处理好的前缀。
• 对于每个冲突，至少需要一次修改（因为不修改就会保留回文），而贪心每次恰好修改一次。
• 修改当前字符为合法字符，不会引入新的冲突，因此局部最优即全局最优。

方法一：贪心

思路及解法

1. 将字符串转为列表以便修改。
2. 从左到右遍历每个位置 i：
   • 检查是否与 s[i-1]（若 i >= 1）或 s[i-2]（若 i >= 2）相同；
   • 若冲突，则从 'a' 到 'z' 中找一个与 s[i-1] 和 s[i-2] 都不同的字符，替换 s[i]，并增加修改计数。
3. 返回修改计数。

代码

class Solution:
    def minChanges(self, s: str) -> int:
        s = list(s)
        n = len(s)
        ans = 0

        for i in range(n):
            conflict = False
            if i >= 1 and s[i] == s[i - 1]:
                conflict = True
            if i >= 2 and s[i] == s[i - 2]:
                conflict = True

            if conflict:
                # 找一个与 s[i-1] 和 s[i-2] 都不同的字符
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    if (i < 1 or c != s[i - 1]) and (i < 2 or c != s[i - 2]):
                        s[i] = c
                        break
                ans += 1

        return ans

复杂度分析

• 时间复杂度：$O(n \cdot 26)$，每个位置最多尝试 26 个字符，实际远小于此，近似 $O(n)$。
• 空间复杂度：$O(n)$，用于存储字符串的列表副本（也可原地修改，额外空间 $O(1)$）。

总结

• 问题转化：禁止长度 2 和长度 3 的回文即可禁止所有回文。
• 贪心修改：从左到右，遇到冲突就改当前字符为合法字符。
• 最少次数：每个冲突必须修改一次，贪心保证不引入新冲突，因此答案就是冲突的次数。
• 通用套路：字符串中禁止回文子串时，通常只需检查相邻和间隔一个的字符。

相关题目

• LC 680. 验证回文字符串 II（删除一个字符判断回文）
• LC 647. 回文子串（统计所有回文子串）
• LC 1328. 破坏回文串（修改一个字符使不是回文）