Break a Palindrome: Greedy Character Replacement

You are given a palindromic string palindrome. Replace exactly one character with any lowercase English letter so that the resulting string is not a palindrome and is the lexicographically smallest one possible. If there is no way to do so, return an empty string.

This is LeetCode 1328: Break a Palindrome.

Why this problem matters

This problem tests whether you can think greedily about lexicographic order. Many string problems ask you to produce the "smallest" result, and the pattern is almost always the same: make the earliest position as small as possible. Here, the palindrome constraint adds a twist. You need to understand how symmetry limits your options and how breaking symmetry in the right place gives you the optimal answer.

Problems involving lexicographic minimization come up frequently in interviews. Once you internalize the greedy principle of "fix the leftmost position first," you will recognize it in dozens of variations.

The key insight

To produce the lexicographically smallest non-palindrome, you want to make the earliest character as small as possible. The smallest character is 'a', so you scan from left to right looking for the first character that is not 'a' and change it to 'a'.

But you only need to scan the first half. Why? Because the string is a palindrome, so the second half mirrors the first. If you change a character in the first half, its mirror in the second half stays the same, which breaks the palindrome. If you changed a character in the second half to 'a', you could always do better by changing its mirror in the first half instead (that would be an earlier position).

There is one special case: if every character in the first half is already 'a' (like "aaa" or "aba"), you cannot make any character smaller. In this situation, you change the last character to 'b'. This produces the smallest possible non-palindrome because you are modifying the latest position and only increasing it by the minimum amount.

Finally, if the string has length 1, it is impossible to break the palindrome with a single replacement. Any single-character string replaced with another single character is still a palindrome. Return an empty string.

The solution

def break_palindrome(palindrome: str) -> str:
    n = len(palindrome)
    if n == 1:
        return ""

    s = list(palindrome)
    for i in range(n // 2):
        if s[i] != 'a':
            s[i] = 'a'
            return "".join(s)

    s[-1] = 'b'
    return "".join(s)

The function converts the string to a list for mutability, then scans the first half. The moment it finds a character that is not 'a', it replaces that character with 'a' and returns immediately. If the loop completes without finding such a character, it means the entire first half is 'a', so it changes the last character to 'b'. The length-1 check at the top handles the impossible case.

Visual walkthrough

The greedy scan through the first half guarantees that you change the earliest possible position. Changing it to 'a' guarantees you pick the smallest possible replacement. These two choices together produce the lexicographically smallest result.

Complexity analysis

The time complexity is O(n) because you scan at most half the string, which is linear. The space complexity is O(n) because you create a list copy of the string to perform the mutation. In languages with mutable strings, you could achieve O(1) extra space, but the output itself is always O(n).

The building blocks

1. Palindrome symmetry property

A palindrome reads the same forwards and backwards. This means s[i] == s[n - 1 - i] for all valid indices. When you change a character in the first half, the corresponding character in the second half stays unchanged, which breaks the symmetry and breaks the palindrome. This property lets you restrict your search to just the first half of the string.

2. Lexicographic greedy: change the earliest position possible

To minimize a string lexicographically, you should always try to make the leftmost character as small as possible. If position 0 can be made smaller, do it there. If not, move to position 1, then position 2, and so on. This greedy left-to-right scan is the standard technique for any "produce the smallest string" problem. Here, "as small as possible" means replacing with 'a', since 'a' is the smallest lowercase letter.

Edge cases

• Single character string like "a". You cannot replace one character and produce a non-palindrome, so return "".
• All same characters like "aaa". The first half is all 'a', so no character can be made smaller. Change the last character to 'b' to get "aab".
• Odd-length palindrome like "aba". The middle character is skipped because changing the middle of an odd-length palindrome does not break the symmetry (the middle character is its own mirror). Scan indices 0 through n // 2 - 1, which skips index 1. Index 0 is 'a', so the loop finds nothing, and you fall through to changing the last character: "abb".
• First character is not 'a' like "bab". Index 0 is 'b', so you immediately change it to 'a' and return "aab".
• String of length 2 like "bb". Index 0 is 'b', so change it to 'a' and return "ab".

From understanding to recall

The algorithm is short, but there are several pieces you need to remember: scan only the first half, look for the first non-'a' character, replace it with 'a', and handle the all-'a' fallback by changing the last character to 'b'. Under interview pressure, it is easy to forget the first-half-only restriction or the edge case for single-character strings.

Spaced repetition helps you internalize these details. You practice writing the greedy scan from scratch at increasing intervals until the logic is automatic. When you see "smallest non-palindrome" in an interview, you do not need to rederive the approach. You write it immediately because you have done it before.

Related posts

• Palindrome Number - Understanding palindrome structure
• Orderly Queue - Greedy string transformation
• Longest Palindromic Substring - Palindrome properties

CodeBricks breaks this problem into its palindrome symmetry and lexicographic greedy building blocks, then drills them independently with spaced repetition. You type each piece from scratch until it becomes automatic. When a greedy string problem shows up in your interview, you recognize the pattern and write it without hesitation.