1328. 破坏回文串

题目链接（中等）

题目描述

给你一个由小写英文字母组成的回文字符串 palindrome，请你将其中 一个 字符用任意小写英文字母替换，使得结果字符串的 字典序最小，且 不是 回文串。

请你返回结果字符串。如果无法做到，则返回一个 空串。

数据范围：

• 1 <= palindrome.length <= 1000
• palindrome 只包含小写英文字母

示例

示例 1：

输入： palindrome = "abccba"
输出： "aaccba"
解释： 存在多种方法可以使 "abccba" 不是回文，例如 "zbccba"、"aaccba" 和 "abacba"。在所有方法中，"aaccba" 的字典序最小。

示例 2：

输入： palindrome = "a"
输出： ""
解释： 不存在替换一个字符使 "a" 变成非回文的方法，所以返回空字符串。

核心思路

目标：让结果字符串字典序最小，且不是回文。

贪心策略：字典序比较从左到右，所以要让靠前的位置尽可能小。

关键观察：因为原串是回文，前半部分和后半部分对称。改前半部分的字符，影响更大（位置更靠前），所以优先改前半部分。

分三种情况：

1. 长度 ≤ 1：只有一个字符，替换后还是它自己（或改成别的但仍是长度 1 的串，长度 1 的串一定是回文），无法破坏回文，返回 ""；
2. 前半部分存在非 'a' 的字符：把最靠左的非 'a' 字符改成 'a'，字典序最小；
3. 前半部分全是 'a'：说明原串形如 "aaaa...aaaa"（因为回文且前半全 a，后半也全 a）。此时把最后一个字符改成 'b'，这是字典序最小的非回文串。

为什么情况 3 改最后一个字符：

• 前半部分全是 'a'，改前面的 'a' 为更大的字母（如 'b'）会使字典序变大；
• 改最后一个字符影响最小（位置最靠后）；
• 把最后一个 'a' 改成 'b'，得到 "aaa...aab"，不是回文，且字典序最小。

举例：

• "abccba"：前半部分 "abc"，第一个非 'a' 是 'b'（下标 1），改成 'a'，得 "aaccba"；
• "aa"：前半部分只有 'a'，改最后一位为 'b'，得 "ab"；
• "aba"：前半部分 "a"，全是 'a'，改最后一位为 'b'，得 "abb"。

---

方法：贪心

思路及解法

1. 若 len(palindrome) <= 1，返回 ""；
2. 将字符串转为列表，方便修改；
3. 遍历前半部分（i 从 0 到 n // 2 - 1）：
   • 若 palindrome[i] != 'a'，把 palindrome[i] 改为 'a'，返回结果；
4. 若前半部分全是 'a'，把最后一个字符改为 'b'，返回结果。

为什么遍历到 n // 2 - 1 而不是 n // 2：

• 对于奇数长度，中间字符改了对回文性没影响（它自己对称自己），改它没有意义；
• 只需考虑前半部分（不含中间字符）。

代码

class Solution:
    def breakPalindrome(self, palindrome: str) -> str:
        n = len(palindrome)
        if n <= 1:
            return ""

        s = list(palindrome)

        # 从左到右找前半部分第一个非 'a' 的字符
        for i in range(n // 2):
            if s[i] != 'a':
                s[i] = 'a'
                return ''.join(s)

        # 前半部分全是 'a'，改最后一个字符为 'b'
        s[-1] = 'b'
        return ''.join(s)

复杂度分析

• 时间复杂度：$O(n)$，遍历前半部分一次。
• 空间复杂度：$O(n)$，字符串转列表。

---

关键细节

1. 为什么长度 ≤ 1 无法破坏回文

长度为 1 的字符串，替换成任何字符仍然是长度 1，而长度 1 的字符串一定是回文。所以无法做到，返回空串。

2. 为什么优先改前半部分

字典序比较从左到右，靠前的位置影响更大。前半部分的位置比后半部分靠前，改前半部分能得到更小的字典序。

而且由于原串是回文，后半部分和前半部分对称，改前半部分的效果和改后半部分对应位置相同，但前半部分位置更靠前，更优。

3. 为什么改成 'a'

'a' 是小写字母中最小的，把非 'a' 改成 'a' 能让字典序尽可能小。

4. 为什么情况 3 改最后一个字符而不是中间

前半部分全是 'a' 时：

• 改任何前半部分的 'a' 为更大的字符，会使字典序变大；
• 改最后一个字符为 'b'，影响的位置最靠后，字典序增加最小；
• 改最后一个字符为 'b' 后，字符串变为 "aaa...aab"，由于首位是 'a'、末位是 'b'，不是回文。

5. 为什么不改中间字符

对于奇数长度，中间字符改了对回文性没有影响（它和它自己对称）。改中间字符既不能破坏回文，又可能使字典序变大，所以不考虑。

6. 边界例子验证

输入	输出	说明
"a"	""	长度 1，无法破坏
"aa"	"ab"	前半全 a，改最后一位
"aba"	"abb"	前半全 a，改最后一位
"abba"	"aaba"	前半 "ab"，第一个非 a 是 'b'，改成 'a'
"aabaa"	"aabab"	前半 "aa" 全 a，改最后一位
"abccba"	"aaccba"	前半 "abc"，第一个非 a 是 'b'，改成 'a'

7. 一个容易错的点

遍历范围是 range(n // 2)，即 0 到 n // 2 - 1。

对于偶数长度 n，n // 2 正好是前半部分的长度；
对于奇数长度 n，n // 2 是前半部分（不含中间字符）的长度。

两种情况下都正确。

---

总结

• 核心思路：贪心，让字典序尽可能小；
• 三种情况：
  1. 长度 ≤ 1：返回 ""；
  2. 前半部分有非 'a'：把最靠左的非 'a' 改成 'a'；
  3. 前半部分全是 'a'：把最后一个字符改成 'b'；
• 为什么遍历前半部分：靠前的位置对字典序影响更大；
• 时间复杂度 $O(n)$，空间复杂度 $O(n)$；
• 通用套路：「字典序最小」→ 从左到右贪心，优先改靠前的位置。

相关题目

• LC 680. 验证回文串 II（最多删一个字符判断回文）
• LC 125. 验证回文串（基础双指针）
• LC 647. 回文子串（统计所有回文子串）
• LC 5. 最长回文子串（中心拓展 / DP）