破坏回文串

难度: Medium

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

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

如果两个字符串长度相同，那么字符串 a 字典序比字符串 b 小可以这样定义：在 a 和 b 出现不同的第一个位置上，字符串 a 中的字符严格小于 b 中的对应字符。例如，"abcc” 字典序比 "abcd" 小，因为不同的第一个位置是在第四个字符，显然 'c' 比 'd' 小。

示例 1：

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

示例 2：

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

提示：

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

Submission

运行时间: 23 ms

内存: 16.0 MB

class Solution:
    def breakPalindrome(self, palindrome: str) -> str:
        if len(palindrome)==1:
            return ""
        for i in range(len(palindrome)//2):
            if palindrome[i]!="a":
                return palindrome[:i]+"a"+palindrome[i+1:]
        return palindrome[:-1]+"b"

Explain

此题解的核心思路是通过尽量少的改动使回文字符串不再是回文的同时字典序最小。首先，检查字符串长度，如果是1，则无法通过改变一个字符使其不是回文，直接返回空字符串。接着，遍历字符串的前半部分，寻找第一个不是'a'的字符，将其替换为'a'，因为'a'是最小的字母，这样可以保证得到的新字符串字典序尽可能小。如果前半部分所有字符都是'a'，则将最后一个字符改为'b'，因为整个字符串替换'a'后仍是回文，所以改变最后一个字符可以确保字符串不是回文，而改为'b'能保持字典序较小。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def breakPalindrome(self, palindrome: str) -> str:
        if len(palindrome)==1:
            return ""  # 如果字符串长度为1，返回空字符串
        for i in range(len(palindrome)//2):  # 只遍历字符串的一半
            if palindrome[i]!="a":
                return palindrome[:i]+"a"+palindrome[i+1:]  # 替换第一个不是'a'的字符为'a'
        return palindrome[:-1]+"b"  # 如果所有字符都是'a'，则将最后一个字符替换为'b'

Explore

在破坏回文串的过程中，目的是使字符串不再是回文的同时，保证字典序尽可能小。字母'a'是所有字母中字典序最小的，因此，将非'a'的字符替换为'a'可以使得修改后的字符串的字典序比替换成其他任何字母都要小。此外，从字符串的前半部分开始寻找第一个非'a'的字符进行替换，可以确保在不影响回文性质的前提下，尽可能减小字典序。

如果一个回文串完全由字符'a'组成，那么不论修改任何一个'a'为其他字符，新生成的字符串都将不再是回文串。选择将最后一个字符'a'改为'b'而不是改变其他位置的'a'，是因为这样可以保持字典序最小（'a'本身就是最小的，只改最后一个'a'为'b'才能最小幅度增加字典序）。此外，由于回文串的对称性，最后一个字符在回文中通常与第一个字符相对应，改变它能有效地破坏回文结构。

长度为1的字符串由单一字符构成，无论这个字符是什么，它总是回文，因为正序和倒序都是相同的（仅一个字符）。在这种情况下，改变这唯一的字符只会将它变成另一个字符，但该字符串仍然是回文（因为它仍然只包含一个相同的字符）。因此，不能通过改变单个字符使长度为1的字符串不再是回文。

遍历字符串的前半部分是基于回文的对称性质。由于回文字符串的后半部分是前半部分的镜像，只需考虑前半部分即可找到破坏回文所需的最小改动点。这种策略在保证最小字典序的同时，减少了需要检查的字符数量，是一种高效的策略。在大多数情况下，这是最优的策略，因为它直接关注于破坏回文的关键点，即对称的中心。但如果有特殊要求，例如最小化改动的字母数或改动的位置，则可能需要考虑其他策略。