1328 - Break a Palindrome

Difficulty: Medium | Pattern: Greedy + String | Company tags: Amazon, Adobe

Problem Statement

Given a palindromic string of lowercase English letters palindrome, replace exactly one character with any lowercase English letter so that the resulting string is not a palindrome and that it is the lexicographically smallest string possible.

Return the resulting string. If there is no way to replace a character to make it not a palindrome, return an empty string.

Example 1:

Input: palindrome = "abccba"
Output: "aaccba"
Explanation: Replace 'b' at index 1 with 'a' → "aaccba" (smaller than replacing 'b' at index 4)

Example 2:

Input: palindrome = "a"
Output: ""
Explanation: Any single character is itself a palindrome, and replacing it with another
character still yields a single-character string, which is also a palindrome. There is
no way to make a length-1 string non-palindromic, so return "".

Approach: Greedy — O(n)

Key insight:

1. Scan left half. Find the first non-'a' character. Replace it with 'a' — this is the lexicographically smallest change AND it breaks the palindrome (since its mirror differs).
2. If no non-'a' exists in the left half (all 'a's), the string is like "aaa...a" or "aaa...a". Replace the last character with 'b' (lexicographically smallest non-'a').
3. If length = 1 → return "".

def breakPalindrome(palindrome: str) -> str:
    n = len(palindrome)
    if n == 1:
        return ""
    
    s = list(palindrome)
    
    # Try to replace first non-'a' in left half with 'a'
    for i in range(n // 2):
        if s[i] != 'a':
            s[i] = 'a'
            return ''.join(s)
    
    # All left half is 'a': change last char to 'b'
    s[-1] = 'b'
    return ''.join(s)

Why Only Check Left Half?

For a palindrome, s[i] == s[n-1-i]. Changing s[i] to 'a' makes s[i] != s[n-1-i] → not a palindrome. We only need to check i < n//2 (not the middle for odd-length, since it mirrors itself and changing it to 'a' may not break it).

Algorithm Flow

Dry Run

palindrome = "abccba" (n=6)

• i=0: s[0]='a' → skip
• i=1: s[1]='b' ≠ 'a' → set s[1]='a' → "aaccba"

Return "aaccba" ✓

palindrome = "aaaa" (n=4, all 'a's)

• Left half [0,1]: both 'a', no non-'a' found
• Replace s[-1] with 'b' → "aaab"

Return "aaab" ✓

Edge Cases

• Single char → return ""
• All 'a's → change last to 'b'
• Odd length like "aba": left half = ['a'], all 'a' → change last to 'b' → "abb"

Complexity

• Time: O(n)
• Space: O(n) for the list

Key Terms

Term	Definition
Greedy choice	Making the locally optimal decision at each step (replace the first non-'a' with 'a') without backtracking, and proving it yields a global optimum.
Lexicographic order	String comparison based on character order at the first differing position — used here to determine the "smallest" valid result.
Palindrome symmetry	The property s[i] == s[n-1-i] for all valid i; breaking it at any one index makes the whole string non-palindromic.
Left half scan	Only examining indices 0 to n//2 - 1, since changing a middle character in an odd-length palindrome doesn't break symmetry.

FAQ

1. Can this be solved without extra space? Not in Python, since strings are immutable — you need a mutable structure like a list (O(n) space) to modify a character in place. In a language with mutable strings (like C++), you could edit in O(1) extra space.
2. What if the input is a single character? Return "" immediately — any replacement of a single character still produces a single-character string, which is always a palindrome.
3. Why do we only scan the left half instead of the whole string? Because of symmetry, changing s[i] for i < n//2 already breaks the palindrome via its mirror s[n-1-i]. Scanning the right half would either duplicate work or, for odd-length strings, incorrectly consider the middle character (whose mirror is itself).
4. What if there were no constraint on lexicographic smallest — just "make it not a palindrome"? Any single-character change that breaks symmetry works; you could pick the first non-'a' character anywhere except the exact middle (odd length) and flip it to any different letter.
5. How would the approach change if replacement had to use a specific alphabet or Unicode set instead of lowercase English letters? The core greedy logic is unchanged — you still replace the first non-smallest-letter character in the left half with the smallest available letter, and fall back to changing the last character to the second-smallest letter if the string is already all smallest letters.

Quick Revision

• Goal: replace exactly one character to make the palindrome non-palindromic and lexicographically smallest.
• Scan indices 0 to n//2 - 1 (left half only); replace the first character that isn't 'a' with 'a'.
• That single change is enough to break symmetry because s[i] != s[n-1-i] afterward.
• If the entire left half is already 'a', the whole string is all 'a's (or all 'a's with an odd middle) — change the last character to 'b'.
• Single-character input always returns "" since no replacement can escape being a palindrome.
• Time O(n), space O(n) (for the mutable list copy in Python).
• Key proof point: changing an earlier index to the smallest letter always beats changing a later index, by lexicographic ordering rules.
• Common bug: scanning the full string instead of just the left half, which risks flipping the middle character of an odd-length palindrome (no effect) or double-processing mirrored pairs.

Related Problems

• Same "greedy leftmost minimal change" idea applied differently: 316 - Remove Duplicate Letters
• Palindrome property manipulation: 5 - Longest Palindromic Substring
• Greedy lexicographically-smallest-result pattern: 402 - Remove K Digits