LeetCode 1328. 破坏回文串

约 6 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节跳动
标签
字符串 贪心
目录

题目描述

✅ 1328. 破坏回文串

题意分析

给定一个由小写字母组成的回文串 palindrome，要求恰好修改一个字符（把它换成任意一个小写字母），使得结果不再是回文串，并且在所有可行结果中字典序最小。如果无论怎么改都做不到，返回空串。

三个条件要一起看：改动次数恰好为 1（不能不改，也不能改两处）、结果必须非回文、在此前提下字典序最小。这是一道「先保证可行性，再在可行解里取最优」的题。

输入本身已经是回文，这个前提非常关键——它意味着 s[i] == s[n-1-i] 对所有 i 成立。所以修改任意一个非中心位置的字符，都会立刻打破它与镜像位置的相等关系，回文性随之破坏；而修改正中间那个字符（仅当长度为奇数时存在）的镜像就是它自己，改完仍然对称，回文性纹丝不动。这一条直接决定了中心位置是「无效位置」，必须排除。

字典序最小的规则要想清楚：长度不变的两个串比字典序，就是从左往右找第一个不同的位置，谁的字符小谁就小。所以越靠左的位置权重越高，且把某位改小的收益永远大于把右边任何位置改小的收益。

约束里字符串长度在 1 到 1000 之间，全是小写字母。长度为 1 是唯一的无解情形：只有一个字符，改成什么都还是长度为 1 的回文串。

边界要留意三点：长度为 1 返回空串而不是原串；长度为奇数时中心下标 n/2 不能改；答案必须是修改后的完整字符串，不是下标也不是字符。

解法：贪心修改

核心思路

输入已经是回文串。修改一个非中心位置后，它与镜像位置不再相等，结果必然不是回文；奇数长度的中心位置即使修改，左右结构仍对称，所以不能选中心。

字典序比较首先看最靠左的不同位置。若前半段存在非 'a' 字符，应把最左侧这样的字符改成 'a'：它是最早可以变小的位置，也取到了该位置的最小字母，任何更靠后的修改都更大。

若前半段全是 'a'，由回文性可知除可能的中心外，其余字符也全是 'a'。此时无法把合法位置改小，只能把一个 'a' 改大；应选择最右侧位置，并改成最小的更大字母 'b'，让变大的影响尽量晚出现。

贪心不变量：扫描前半段时，已经跳过的位置都是 'a'，它们无法合法地变得更小；遇到的第一个非 'a' 就是全局最早可降低的位置。

正确性：若存在该位置，修改为 'a' 会破坏一对镜像且在首个可优化位置达到最小值，因此全局最优。若不存在，所有非中心位都是 'a'，任何合法方案都必须把某位增大；最右位置的 'b' 比任何更左或更大的修改字典序小。长度为 1 时只有中心位置，无法破坏回文，返回空串。

解题步骤

  1. 若长度为 1，返回空串。
  2. 将字符串转为可修改字符数组，只扫描下标 [0, n / 2)，自然排除奇数中心。
  3. 找到第一个不是 'a' 的字符，将其改为 'a' 并立即返回。
  4. 若前半段全为 'a'，将最后一个字符改为 'b' 后返回。

abccba 在下标 1 首次遇到 'b'，得到 aaccba；aba 的前半段只有 'a'，不能修改中心，于是将末位改为 'b' 得 abb；aa 得到 ab；单字符 a 返回空串。

代码实现

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)$，用于可修改字符数组和返回字符串；除输出表示外只使用常数变量。

关键点总结

  • 修改非中心位置必然破坏回文，因此构造时无需再次验证。
  • 能变小时，修改最左侧非 'a' 为 'a'；只能变大时，修改末位为 'b'。
  • 只扫描前半段可以同时利用回文对称性并避开奇数中心。
  • 长度为 1 是唯一无解情况。

易错点总结

  • 扫描包含中心：aba 若把中心 'b' 改成 'a' 会得到仍是回文的 aaa。
  • 找到非 'a' 后继续修改：会违反只能改一个字符的要求。
  • 前半段全为 'a' 时修改首位：aa 会得到 ba，大于正确答案 ab。
  • 末位改成 'z'：虽然能破坏回文，但 'b' 是更小的合法选择。
  • 漏掉长度 1：把单字符改成任何字母仍然是回文，不能返回修改后的字符。

相似题目

题目 难度 考察点
125. 验证回文串 简单 双指针判定回文的基本功，还要处理非字母数字字符的跳过
680. 验证回文串 II 简单 允许删一个字符，双指针失配时分两支各试一次，是「一次修改」的删除版
5. 最长回文子串 中等 中心扩展要同时枚举奇偶两种中心，与本题「中心不可改」互为镜像知识点
647. 回文子串 中等 与 5 同一扩展框架，把取最长换成计数
516. 最长回文子序列 中等 子序列不要求连续，需要区间 DP 而非中心扩展
1312. 让字符串成为回文串的最少插入次数 困难 答案等于长度减去最长回文子序列，体现「构造回文」与「破坏回文」的对偶
214. 最短回文串 困难 求最长回文前缀，用 KMP 的 next 数组把 $O(n^2)$ 压到 $O(n)$
564. 寻找最近的回文数 困难 同为「构造最优回文相关串」，但候选只有镜像前缀的三种微调，边界极多
1400. 构造 K 个回文字符串 中等 只需统计奇数次字符个数与 k 比较，是回文性质的计数化运用
409. 最长回文串 简单 同样靠奇偶计数，重点是最多留一个奇数字符放中心
738. 单调递增的数字 中等 同为「一次局部改动 + 后缀取极值」的贪心，方向是取最大而非最小
670. 最大交换 中等 恰好一次交换求最大值，要从右往左记录最大数字的位置
402. 移掉 K 位数字 中等 字典序最小的删除版本，需要单调栈而非单点贪心
316. 去除重复字母 中等 字典序最小 + 每字符恰好保留一个，单调栈还要配合剩余计数判断能否弹出