Break a Palindrome — Solution in Python, Java & C++
Break a Palindrome solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on strings and greedy.
Break a Palindrome is a medium coding problem on strings and greedy, asked in Amazon, Microsoft and Meta interviews.
- Difficulty: Medium
- Topics: Strings, Greedy
- Asked at: Amazon, Microsoft, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a palindrome of lowercase English letters. Replace exactly one of its characters with a different lowercase letter so that the result is not a palindrome, and among all such results return the lexicographically smallest one.
If no replacement can break the palindrome, return an empty string.
Example 1
Input: palindrome = "kayak"
Output: aayak
Explanation: Turning the first `k` into `a` breaks the symmetry and is as small as possible.
Example 2
Input: palindrome = "aba"
Output: abb
Explanation: The first half is already all `a`; changing the middle keeps a palindrome, so the last letter becomes `b`.
Example 3
Input: palindrome = "z"
Output: ""
Explanation: Every single letter is a palindrome.
Constraints
1 <= palindrome.length <= 1000palindrome consists of lowercase English letterspalindrome reads the same forwards and backwards
Hints for Break a Palindrome
Hint 1
A one-letter string can never stop being a palindrome.
Hint 2
To make the string as small as possible, lower the earliest letter you can — to
a.Hint 3
Only the first half matters (changing the middle of an odd-length string keeps it a palindrome). If the first half is all
a, the best you can do is change the last letter tob.
How to solve Break a Palindrome
The smallest result comes from writing an a as early as possible; if that is impossible without keeping the string a palindrome, the least damaging change is to raise the very last letter to b.
Approach
- If the length is 1, return the empty string.
- Scan
ifrom 0 whilei < n / 2(the first half, excluding a middle letter). At the firstpalindrome[i] != 'a', set it to'a'and return. - Otherwise every letter outside the middle is
a: set the last letter to'b'and return.
Why it works
Changing position i in the first half breaks the symmetry with its mirror n − 1 − i, so the result is not a palindrome; making it a at the earliest such position gives the smallest possible string, since any change at an earlier position would have to raise an a. Changing the middle letter of an odd-length string keeps it a palindrome. If the first half is all a, any change must raise some letter, and raising the last one to b keeps the longest possible prefix of as, so it is the smallest.
Complexity
- Time —
O(n) - Space —
O(n) for the copy
Pitfalls
- Changing the middle character of an odd-length palindrome does not break it (
aba→aaa). aaaamust becomeaaab, notbaaa.- Length 1 has no answer — return an empty string.
Reference solution
Python
def breakPalindrome(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)Java
public static String breakPalindrome(String palindrome) {
int n = palindrome.length();
if (n == 1) return "";
char[] chars = palindrome.toCharArray();
for (int i = 0; i < n / 2; i++) {
if (chars[i] != 'a') {
chars[i] = 'a';
return new String(chars);
}
}
chars[n - 1] = 'b';
return new String(chars);
}C++
string breakPalindrome(string palindrome) {
int n = (int)palindrome.size();
if (n == 1) return "";
for (int i = 0; i < n / 2; i++) {
if (palindrome[i] != 'a') {
palindrome[i] = 'a';
return palindrome;
}
}
palindrome[n - 1] = 'b';
return palindrome;
}JavaScript
var breakPalindrome = function(palindrome) {
var n = palindrome.length;
if (n === 1) return "";
for (var i = 0; i < Math.floor(n / 2); i++) {
if (palindrome[i] !== "a") return palindrome.substring(0, i) + "a" + palindrome.substring(i + 1);
}
return palindrome.substring(0, n - 1) + "b";
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Greedy Algorithms