#1328

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Break a Palindrome

Given a palindrome, change exactly one character to make it non-palindromic and lexicographically smallest using a greedy approach.

string greedy

Problem Statement

You are given a string palindrome consisting of lowercase English letters that is guaranteed to read the same forwards and backwards. Modify exactly one character so that the string no longer forms a palindrome and becomes the lexicographically smallest string possible. Return the resulting string after the change.

If the string has length 1, it is impossible to perform any replacement to break the palindrome, so in that case return an empty string. Lexicographical order means that in the first differing position between two strings, the string with the smaller character is considered smaller.

Examples

Example 1

Input: palindrome = "abccba"

Output: "aaccba"

There are many ways to make "abccba" not a palindrome, such as "zbccba", "aaccba", and "abacba". Of all the ways, "aaccba" is the lexicographically smallest.

Example 2

Input: palindrome = "a"

Output: ""

There is no way to replace a single character to make "a" not a palindrome, so return an empty string.

Constraints

1 <= palindrome.length <= 1000
palindrome consists of only lowercase English letters.

Solution Approach

Greedy Left-to-Right Replacement

Scan the palindrome from left to right. Replace the first character that is not 'a' with 'a'. This ensures the smallest lexicographical change while breaking the palindrome immediately.

Handle Single-Character or All-'a' Edge Cases

If the palindrome length is 1, return an empty string. If all characters are 'a', change the last character to 'b' to break the palindrome while making the minimal lexicographical impact.

Validation of Non-Palindromic Result

After performing the replacement, confirm that the resulting string is no longer a palindrome. This step ensures the greedy choice correctly produced a valid output for the problem.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The algorithm runs in O(n) time because it scans the string once and performs at most one character replacement. Space complexity is O(n) due to creating a copy of the string for modification.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Greedy

First, we check if the length of the string is $1$. If it is, we directly return an empty string.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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)

Continue Practicing

#1400 construct k palindrome strings #1405 longest happy string #1247 minimum swaps to make strings equal