1328. 破坏回文串
题目描述
输入一个只含小写英文字母的回文串 palindrome。
把其中恰好一个字符换成任意小写字母，使得结果不再是回文串。在所有可行的结果中，返回字典序最小的那个。
如果怎样替换都无法让它不是回文串，返回空串 ""。
字典序比较：长度相同的两个串，从左往右找到第一个不同的位置，该位置字符较小的串字典序更小。
示例 1
输入：palindrome = "abccba" 输出："aaccba"
解释：可行结果有 zbccba、aaccba、abacba 等，其中 aaccba 最小。
示例 2
输入：palindrome = "a" 输出：""
解释：只有一个字符，换成什么都还是回文串。
数据范围
1 <= palindrome.length <= 1000palindrome只含小写英文字母。
解题思路
长度为 1 时任何改法都还是回文，返回空串。否则要让字典序最小，就把尽量靠前的字符改小：在前一半里找第一个不是 a 的字符，改成 a。只在前一半找，是因为奇数长度的中心字符改了仍是回文。如果前一半全是 a，任何位置都无法改小，只好把最后一个字符改成 b，把“变大”放在最不重要的位置。
为什么正确
palindrome[:i] 全是 a，改这些位置只会让字典序变大。
复杂度分析
时间 O(n)，空间 O(n)（字符列表）。
易错点
在整个串里找第一个非 a 字符。对于 "aba"，中心的 b 改成 a 得到 "aaa" 仍是回文，正确答案是 "abb"。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def breakPalindrome(self, palindrome: str) -> str:
n = len(palindrome)
if n == 1:
return ""
s = list(palindrome)
for i in range(n // 2):
if s[i] != 'a':
s[i] = 'a'
return "".join(s)
s[-1] = 'b'
return "".join(s)class Solution {
public String breakPalindrome(String palindrome) {
int n = palindrome.length();
if (n == 1) {
return "";
}
char[] s = palindrome.toCharArray();
for (int i = 0; i < n / 2; i++) {
if (s[i] != 'a') {
s[i] = 'a';
return new String(s);
}
}
s[n - 1] = 'b';
return new String(s);
}
}class Solution {
public:
string breakPalindrome(string palindrome) {
int n = palindrome.size();
if (n == 1) {
return "";
}
string s = palindrome;
for (int i = 0; i < n / 2; i++) {
if (s[i] != 'a') {
s[i] = 'a';
return s;
}
}
s[n - 1] = 'b';
return s;
}
};func breakPalindrome(palindrome string) string {
n := len(palindrome)
if n == 1 {
return ""
}
s := []byte(palindrome)
for i := 0; i < n/2; i++ {
if s[i] != 'a' {
s[i] = 'a'
return string(s)
}
}
s[n-1] = 'b'
return string(s)
}var breakPalindrome = function(palindrome) {
const n = palindrome.length;
if (n === 1) {
return "";
}
const s = palindrome.split("");
for (let i = 0; i < Math.floor(n / 2); i++) {
if (s[i] !== 'a') {
s[i] = 'a';
return s.join("");
}
}
s[n - 1] = 'b';
return s.join("");
};function breakPalindrome(palindrome: string): string {
const n = palindrome.length;
if (n === 1) {
return "";
}
const s = palindrome.split("");
for (let i = 0; i < Math.floor(n / 2); i++) {
if (s[i] !== 'a') {
s[i] = 'a';
return s.join("");
}
}
s[n - 1] = 'b';
return s.join("");
}