Why does replacing the first non-'a' character produce the smallest string in Break a Palindrome?

Because lexicographical order prioritizes earlier characters, changing the leftmost non-'a' ensures minimal increase in string order while breaking the palindrome.

What should I do if the palindrome is a single character?

It is impossible to break a single-character palindrome, so the function should return an empty string.

How do I handle a palindrome composed entirely of 'a's?

Change the last character to 'b' to break the palindrome while keeping the string as small as possible lexicographically.

Does the approach differ for odd-length vs even-length palindromes?

No, the greedy left-to-right strategy applies uniformly, with the middle character naturally handled in the scan.

Can GhostInterview provide the step-by-step replacement reasoning?

Yes, it explains which character to replace and why, ensuring the final string is the minimal non-palindrome solution.

#1328

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

破坏回文串

给你一个由小写英文字母组成的回文字符串 palindrome ，请你将其中一个字符用任意小写英文字母替换，使得结果字符串的字典序最小，且不是回文串。请你返回结果字符串。如果无法做到，则返回一个空串。如果两个字符串长度相同，那么字符串 a 字典序比字符串 b 小可以这样定义：在 a…

字符串贪心

题目描述

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

lightbulb

解题思路

方法一：贪心

我们先判断字符串的长度是否为 $1$ ，若是则直接返回空串。

否则，我们从左到右遍历字符串的前半部分，找到第一个不为 'a' 的字符，将其改为 'a' 即可。如果不存在这样的字符，那么我们将最后一个字符改为 'b' 即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def breakPalindrome(self, palindrome: str) -> str:
        n = len(palindrome)
        if n == 1:
            return ""
        s = list(palindrome)
        i = 0
        while i < n // 2 and s[i] == "a":
            i += 1
        if i == n // 2:
            s[-1] = "b"
        else:
            s[i] = "a"
        return "".join(s)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the input length is 1; that's the impossible case.
question_mark
Ask why replacing the first non-'a' character guarantees lexicographical minimality.
question_mark
Consider edge cases like all 'a's or even vs odd length palindromes.

warning

常见陷阱

外企场景

error
Failing to handle the single-character palindrome correctly.
error
Replacing a later character instead of the first non-'a', producing a non-minimal string.
error
Forgetting to check if the resulting string is still a palindrome after replacement.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow replacing multiple characters to break the palindrome and find the lexicographically smallest result.
arrow_right_alt
Return all possible non-palindromic strings from a single replacement, not just the smallest.
arrow_right_alt
Apply the same greedy replacement logic to uppercase letters or mixed-case palindromes.

help

常见问题

外企场景

继续练习

#1400 构造 K 个回文字符串 #1405 最长快乐字符串 #1247 交换字符使得字符串相同