LeetCode 1328 - Break a Palindrome

Difficulty: 🟡 Medium
Topics: String, Greedy

Solution

Problem Understanding

The problem asks us to modify a given palindromic string in such a way that it is no longer a palindrome while ensuring that the resulting string is the lexicographically smallest possible. A palindrome is a string that reads the same forwards and backwards. In this problem, the input palindrome consists only of lowercase English letters and has a length between 1 and 1000.

The key points to understand are: we are allowed to replace exactly one character and the goal is not just to break the palindrome, but also to ensure that the resulting string is as small as possible in lexicographical order. If it is impossible to break the palindrome (for example, if the string has only one character), we return an empty string.

Edge cases include single-character palindromes, palindromes made entirely of 'a' characters, and palindromes with odd lengths where the middle character cannot affect lexicographical order if it is the smallest possible character.

Approaches

Brute Force Approach

A brute-force approach would try replacing each character in the string with every possible lowercase letter ('a' to 'z') and check if the result is a palindrome. Among all non-palindromic results, we would select the lexicographically smallest one. While this guarantees correctness, it is extremely inefficient: for a string of length n, we would generate 25 * n candidates and check each for palindrome status, giving a time complexity of O(n^2) because palindrome checking is O(n).

Optimal Approach

The optimal solution leverages two observations:

To achieve the lexicographically smallest string, we want to replace the leftmost character that is not 'a' with 'a'. Changing a later character or a 'a' character does not minimize lexicographical order.
For strings of odd length, the middle character does not need to be changed if all characters are 'a' because changing it does not affect lexicographical ordering advantage. If all characters are 'a', the best we can do is change the last character to 'b'.

This insight allows us to scan the first half of the string (excluding the middle character if the length is odd) and replace the first non-'a' character with 'a'. If no such character exists, replace the last character with 'b'. This approach is O(n) in time and O(1) in space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Try replacing each character with each letter and check palindrome
Optimal	O(n)	O(n)	Scan first half, replace first non-'a' with 'a', else last character with 'b'

Algorithm Walkthrough

If the input string has length 1, return an empty string because a single-character palindrome cannot be broken.
Convert the input string to a list of characters for easy mutation.
Loop through the first half of the string (index 0 to n//2 - 1):
If the current character is not 'a', replace it with 'a' and return the joined string.
If all characters in the first half are 'a', replace the last character with 'b'.
Return the modified string.

Why it works: Replacing the leftmost non-'a' character guarantees lexicographical minimization because changing any character further to the right would produce a larger string. If all characters are 'a', the only way to break the palindrome is by changing the last character, which is also the lexicographically minimal adjustment possible.

Python Solution

class Solution:
    def breakPalindrome(self, palindrome: str) -> str:
        n = len(palindrome)
        if n == 1:
            return ""
        
        chars = list(palindrome)
        for i in range(n // 2):
            if chars[i] != 'a':
                chars[i] = 'a'
                return "".join(chars)
        
        chars[-1] = 'b'
        return "".join(chars)

This implementation first handles the trivial case of a single-character string. It then converts the string to a list to allow in-place mutation. By scanning only the first half, it guarantees that the palindrome is broken in the lexicographically smallest way. Finally, if all first-half characters are 'a', it changes the last character to 'b' to break the palindrome minimally.

Go Solution

func breakPalindrome(palindrome string) string {
    n := len(palindrome)
    if n == 1 {
        return ""
    }
    
    chars := []byte(palindrome)
    for i := 0; i < n/2; i++ {
        if chars[i] != 'a' {
            chars[i] = 'a'
            return string(chars)
        }
    }
    
    chars[n-1] = 'b'
    return string(chars)
}

The Go solution follows the same logic. Conversion of the string to a byte slice allows mutable operations. Single-character handling and last-character replacement for all-'a' strings are implemented identically.

Worked Examples

Example 1: `"abccba"`

Step	i	chars	Action
Initial	-	['a','b','c','c','b','a']	-
0	0	['a','b','c','c','b','a']	'a' is 'a', skip
1	1	['a','b','c','c','b','a']	'b' != 'a', replace with 'a'
Result	-	['a','a','c','c','b','a']	Return `"aaccba"`

Example 2: `"a"`

Step	i	chars	Action
Initial	-	['a']	Length 1, return `""`

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We scan at most half of the string once and perform at most one replacement
Space	O(n)	We convert the string to a list/byte slice for mutation

The complexity is efficient because we only make one pass over the first half and use constant additional space aside from the mutable copy.

Test Cases

# Provided examples
assert Solution().breakPalindrome("abccba") == "aaccba"  # standard case
assert Solution().breakPalindrome("a") == ""            # single character edge case

# Additional cases
assert Solution().breakPalindrome("aa") == "ab"          # all 'a' two-character string
assert Solution().breakPalindrome("aaa") == "aab"        # odd-length all 'a'
assert Solution().breakPalindrome("aba") == "abb"        # minimal change in odd palindrome
assert Solution().breakPalindrome("abcba") == "aacba"    # first non-a character in first half
assert Solution().breakPalindrome("zzzz") == "azz"       # first non-a character is 'z'
assert Solution().breakPalindrome("aabaa") == "aaaab"    # all 'a' except middle

Test	Why
`"abccba"`	Normal case, lexicographically smallest change
`"a"`	Single-character palindrome cannot be changed
`"aa"`	All characters 'a', minimal length > 1
`"aaa"`	Odd-length all 'a', middle cannot help
`"aba"`	Odd-length palindrome, first non-'a' early
`"abcba"`	First non-'a' not at beginning
`"zzzz"`	All identical, not 'a'
`"aabaa"`	Middle character does not influence lexicographical order

Edge Cases

Single-character strings: Strings like "a" or "z" cannot be made non-palindromic. The implementation explicitly checks for len(palindrome) == 1 and returns an empty string.

All 'a' strings: Strings such as "aa" or "aaaa" require changing the last character to 'b' to break the palindrome minimally. The code handles this by checking the first half and replacing the last character if no replacement occurs earlier.

Odd-length palindromes: For palindromes like "aba" or "aaa", the middle character cannot be changed to 'a' to minimize lexicographical order if it is already 'a'. The algorithm correctly only scans the first half and adjusts the last character if needed, ensuring both correctness and minimal lexicographical output.