Break a Palindrome
Break a Palindrome is a medium arrays & hashing problem solved with the two pointer pattern.
The best approach, optimal (greedy on the first half), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every single-letter change) up.
Problem
You are given a string palindrome of lowercase English letters that reads the same forwards and backwards. Change exactly one character to any other lowercase letter so that the result is not a palindrome, and among all such results return the lexicographically smallest one.
If no single change can break the palindrome, return an empty string.
Examples
Example 1
- Input
palindrome = "racecar"- Output
"aacecar"- Why
- Turning the first 'r' into 'a' breaks the mirror and gives the smallest possible string.
Example 2
- Input
palindrome = "aba"- Output
"abb"- Why
- Changing the middle 'b' keeps a palindrome, and the outer letters are already 'a', so the last letter becomes 'b'.
Example 3
- Input
palindrome = "q"- Output
""- Why
- Any single letter is a palindrome, so there is nothing valid to return.
Constraints
1 <= palindrome.length <= 1000palindromecontains only lowercase English letters and is a palindrome.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 16 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every single-letter change) | O(26 · n²) | O(n) |
| Optimal (greedy on the first half) | O(n) | O(n) |
1Brute force (try every single-letter change)
O(26 · n²)26n candidate strings, each built and checked in O(n).O(n)One candidate string and the best answer.Try every position and every replacement letter. Keep each result that is not a palindrome, and return the lexicographically smallest one.
- For each index i and each letter c from 'a' to 'z' with c != palindrome[i], build the changed string.
- If it is not a palindrome and is smaller than the best so far, keep it.
- Return the best string, or "" if nothing was found.
class Solution {
public String breakPalindrome(String palindrome) {
String best = null;
char[] s = palindrome.toCharArray();
for (int i = 0; i < s.length; i++) {
char orig = s[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == orig) continue;
s[i] = c;
String cand = new String(s);
if (!isPal(cand) && (best == null || cand.compareTo(best) < 0)) best = cand;
}
s[i] = orig;
}
return best == null ? "" : best;
}
private boolean isPal(String t) {
for (int i = 0, j = t.length() - 1; i < j; i++, j--) {
if (t.charAt(i) != t.charAt(j)) return false;
}
return true;
}
}class Solution:
def breakPalindrome(self, palindrome: str) -> str:
best = None
s = list(palindrome)
for i in range(len(s)):
orig = s[i]
for c in "abcdefghijklmnopqrstuvwxyz":
if c == orig:
continue
s[i] = c
cand = "".join(s)
if cand != cand[::-1] and (best is None or cand < best):
best = cand
s[i] = orig
return "" if best is None else bestclass Solution {
bool isPal(const string& t) {
for (int i = 0, j = (int)t.size() - 1; i < j; i++, j--) {
if (t[i] != t[j]) return false;
}
return true;
}
public:
string breakPalindrome(string palindrome) {
bool found = false;
string best;
string s = palindrome;
for (int i = 0; i < (int)s.size(); i++) {
char orig = s[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == orig) continue;
s[i] = c;
if (!isPal(s) && (!found || s < best)) {
best = s;
found = true;
}
}
s[i] = orig;
}
return found ? best : "";
}
};function breakPalindrome(palindrome) {
const isPal = (t) => {
for (let i = 0, j = t.length - 1; i < j; i++, j--) {
if (t[i] !== t[j]) return false;
}
return true;
};
let best = null;
const s = palindrome.split("");
for (let i = 0; i < s.length; i++) {
const orig = s[i];
for (let code = 97; code <= 122; code++) {
const c = String.fromCharCode(code);
if (c === orig) continue;
s[i] = c;
const cand = s.join("");
if (!isPal(cand) && (best === null || cand < best)) best = cand;
}
s[i] = orig;
}
return best === null ? "" : best;
}2Optimal (greedy on the first half)
O(n)At most half the string is scanned once.O(n)A mutable copy of the string for the result.The smallest result comes from writing an 'a' at the leftmost position where it changes something. Scan the first half (the middle of an odd string is skipped because changing it keeps the mirror). The first letter that is not 'a' becomes 'a'. If the whole first half is 'a', every change makes the string bigger, so the least harmful change is turning the last letter into 'b'.
- If n == 1, return "".
- For i from 0 to n / 2 - 1: if s[i] != 'a', set s[i] = 'a' and return s.
- Otherwise set s[n - 1] = 'b' and return s.
class Solution {
public String breakPalindrome(String palindrome) {
int n = palindrome.length();
if (n == 1) return "";
char[] s = palindrome.toCharArray();
for (int i = 0; i < n / 2; i++) {
if (s[i] != 'a') {
s[i] = 'a';
return new String(s);
}
}
s[n - 1] = 'b';
return new String(s);
}
}class Solution:
def breakPalindrome(self, 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[n - 1] = "b"
return "".join(s)class Solution {
public:
string breakPalindrome(string palindrome) {
int n = 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;
}
};function breakPalindrome(palindrome) {
const n = palindrome.length;
if (n === 1) return "";
const s = palindrome.split("");
for (let i = 0; i < Math.floor(n / 2); i++) {
if (s[i] !== "a") {
s[i] = "a";
return s.join("");
}
}
s[n - 1] = "b";
return s.join("");
}Edge cases to test
- Length 1: always return the empty string
- All 'a's, like "aaaa": the last letter must become 'b'
- Odd length where only the middle letter is not 'a', like "aza"
- The first non-'a' letter is at index 0
Hints
Hint 1
To get the smallest string, you want to place an 'a' as far left as possible.
Hint 2
Only look at the first half: changing the exact middle of an odd-length string never breaks the palindrome.
Hint 3
If the first half is all 'a's, every change makes the string larger, so make the smallest increase at the very end.
FAQ
What is the best time complexity for Break a Palindrome?
Optimal (greedy on the first half) runs in O(n) time and O(n) extra space. At most half the string is scanned once.
Which pattern does Break a Palindrome use?
It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.
Is there a brute force solution for Break a Palindrome?
Yes. Brute force (try every single-letter change) takes O(26 · n²) time and O(n) space. Try every position and every replacement letter.
Which edge cases should I test for Break a Palindrome?
Length 1: always return the empty string; All 'a's, like "aaaa": the last letter must become 'b'; Odd length where only the middle letter is not 'a', like "aza"; The first non-'a' letter is at index 0.