[LeetCode] 每日一题 1328. 破坏回文串

题目链接

https://leetcode.cn/problems/break-a-palindrome

题目描述

给你一个由小写英文字母组成的回文字符串 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 只包含小写英文字母。

解题思路

本题的核心在于最小字典序和破坏回文结构，其实是一个简单的贪心问题，属于脑筋急转弯类型

1. 回文串的特点

   • 由于字符串是回文，对称结构使得左右两边的字符相同

   • 要想让它变成非回文，我们只需改变其中一个字符

2. 贪心策略

   • 尽量让字典序最小：优先将左半部分的非 'a' 变为 'a'，这样可以最小化影响

   • 特殊情况：如果整个字符串都是 'a'，那么将最后一个字符改成 'b'，保证非回文，同时字典序尽可能小

3. 边界情况

   • 长度为 1 的回文串无法修改为非回文，直接返回 ""

代码实现

class Solution {
    public String breakPalindrome(String palindrome) {
        int n = palindrome.length();
        if (n <= 1) {
            return "";
        }
        char[] s = palindrome.toCharArray();
        for (int i = 0; i * 2 + 1 < n; i++) {
            if (s[i] != 'a') {
                s[i] = 'a';
                return new String(s);
            }
        }
        s[n - 1] = 'b';
        return new String(s);
    }
}

复杂度分析

• 时间复杂度：只需遍历字符串的一半，即 O(n/2)，最终仍为 O(n)

• 空间复杂度：只使用了一个字符数组 s，开销为 O(n)（但可以直接修改 char[]，避免额外存储）

总结

这道题的关键在于理解回文的对称性，并利用贪心策略快速找到最优解：

• 尽量让字典序最小，优先修改前半部分的非 'a' 为 'a'

• 特殊情况处理，如果字符串全是 'a'，改最后一个字符为 'b'

与昨天的题目相比，这道题更像是一道思维题，一旦想通了核心逻辑，代码实现非常简单

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。