LeetCode 1328. 破坏回文串
题目描述
题意分析
输入保证是只含小写英文字母的回文串，需要恰好替换一个位置的字符，使结果不再是回文，并在所有可行结果中取字典序最小者。不能删除、插入或修改多个位置。
字典序由第一个不同位置的字符决定。长度为一时，换成任何字符仍是回文，必须返回空串；长度大于一时总能通过破坏一对对称字符得到非回文。
解法：贪心修改
核心思路
[!blue]
原串是回文，一对对称位置字符相同。只修改其中一个非中心位置为不同字符，就会让这对不再匹配，足以破坏回文；奇数长度的中心与自身对应，单独改它不会破坏任何对称关系。
如果能够把某个可修改位置变小，应该尽早发生变化，并把该位置改成最小字母
a。因此从左到右检查前半段，第一个不是a的位置就是最早可降低字典序的位置，改成a后立即返回。只看前半段就够：后半段的每个字符都在前半段有一个相同的对称字符，如果后面能变小，前面也能更早变小；同时前半段不包含奇数中心，不会选到无效修改。
如果前半段全部是
a，由对称性可知所有非中心位置都已经是a，不存在有效的变小操作。此时只能让某一位置变大，应将变化推到最右端，并只改为最小的更大字母b。末位与首位不再相同，结果合法，并且字典序增幅最小。
解题步骤
- 长度为一时返回空串，其余情况复制到可修改字符缓冲。
- 只遍历下标
[0, n / 2)，寻找最靠左的非a字符。- 找到后改为
a并立即返回，保证只修改一个位置。- 若没有找到，将最后一位改为
b，返回结果。
代码实现
class Solution {
public String breakPalindrome(String palindrome) {
int n = palindrome.length();
if (n == 1) {
return "";
}
char[] chars = palindrome.toCharArray();
// 只看前半段，利用回文对称性并排除奇数中心。
for (int i = 0; i < n / 2; i++) {
if (chars[i] != 'a') {
chars[i] = 'a';
return new String(chars);
}
}
// 没有可以变小的位置，就让增加发生在最右侧。
chars[n - 1] = 'b';
return new String(chars);
}
}
func breakPalindrome(palindrome string) string {
if len(palindrome) == 1 {
return ""
}
chars := []byte(palindrome)
// 只看前半段，利用回文对称性并排除奇数中心。
for i := 0; i < len(chars)/2; i++ {
if chars[i] != 'a' {
chars[i] = 'a'
return string(chars)
}
}
// 没有可以变小的位置，就让增加发生在最右侧。
chars[len(chars)-1] = 'b'
return string(chars)
}
复杂度分析
- 时间复杂度：$O(n)$，扫描和构造返回字符串均为线性。
- 空间复杂度：$O(n)$，需要可修改的字符缓冲，返回字符串另占线性空间。
关键点总结
[!green]
- 中心位置不能破坏回文性。
- 只修改一个字符，命中后立即结束。
- 前半段的对称信息足以判断是否还有可变小位置。
易错点总结
[!yellow]
- 奇数中心不能用来破坏回文，扫描范围不能包含它。
- 找到可降低位置后继续修改，会违反恰好改变一个字符的限制。
- 没有可降低位置时改首位，会比把增加放在末尾得到更大的字典序。
- 末位只需从
a改成b，改成更大字母不会增加合法性，只会让结果更差。- 长度为一没有合法非回文结果，不能强行返回修改后的单字符。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 2697. 字典序最小回文串 | 简单 | 原题修改字符使字符串成为字典序最小回文，本题只改一位破坏回文，优化方向相反。 |
| 670. 最大交换 | 中等 | 同样一次操作优先改善最高影响位置，本题求字典序最小且要破坏对称，原题求最大整数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！