Break a Palindrome Algorithm

Quick Overview

Practice the greedy algorithm for breaking a palindrome into the lexicographically smallest non-palindrome by one character replacement. The solution explains scanning the left half, skipping the middle character, changing the first non-a to a, handling all-a cases, proving correctness, and analyzing complexity.

Algorithm Prompt: Break a Palindrome to the Lexicographically Smallest Non-Palindrome

Given a palindromic string of lowercase English letters with length from 1 to 1,000, replace exactly one character so that:

The result is no longer a palindrome.
The result is the lexicographically smallest possible string among all valid one-character replacements.

Return the resulting string, or an empty string if it cannot be done.

Constraints & Assumptions

The input string is already a palindrome.
You must replace exactly one character.
The output must be lowercase English letters.
Lexicographic order is compared from left to right.
Length 1 is impossible because any one-character string is a palindrome.

Clarifying Questions to Ask Guidance

Is the input guaranteed to be a palindrome?
Can I replace a character with the same character, or must it change? Assume it must change.
Should I return an empty string for impossible cases?
Are only lowercase English letters allowed?

What a Strong Answer Covers Guidance

Recognizes that changing the earliest possible non- a character in the left half to a gives the smallest result.
Explains why the middle character of an odd-length palindrome should be ignored.
If the left half is all a , changes the last character to b .
Handles length 1 by returning an empty string.
Provides time complexity $O(n)$ and space complexity $O(n)$ or $O(1)$ depending on string mutability.

Follow-up Questions Guidance

Why do we only scan the left half?
Why not change the middle character in an odd-length palindrome?
What happens for strings like aaa or aba ?
How would the algorithm change if uppercase letters were allowed?
Can you prove the greedy choice is optimal?

Quick Overview