Break a Palindrome solution and explanation
9 more videos on this problem
Leetcode problem Break a PalindromeErrichto Algorithms · 8:59 · 39K views
Break a Palindrome | Leetcode 1328 | Live coding session 🍳🍳🍳Coding Decoded · 9:07 · 13K views
Break a Palindrome | Easy Explanation | Leetcode 1328 | codestorywithMIKcodestorywithMIK · 15:06 · 12K views
Leetcode - Break a Palindrome (Python)Timothy H Chang · 4:56 · 5K views
LeetCode 1328 - Break a PalindromeLight Of Truth · 13:54 · 1K views
Daily Leetcode #923: Oct 10, 2022 - 1328. Break a PalindromeProgramming Live with Larry · 9:33 · 1K views
Break a Palindrome | LeetCode 1328 | Java | @LearnOverflowLearn Overflow · 8:48 · 993 views
Amazon Coding Interview Question | Leetcode 1328 | Break a PalindromeWorkWithGoogler · 3:42 · 963 views
Leetcode 1328: Break a PalindromeAlgorithms Casts · 11:46 · 375 views
Break a Palindrome|| Leetcode - 1328|| Java || #DLCNaniCodes · 6:32 · 327 views
The problem
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 one possible.
Return the resulting string. If there is no way to replace a character to make it not a palindrome, return an empty string.
A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, a has a character strictly smaller than the corresponding character in b. For example, "abcc" is lexicographically smaller than "abcd" because the first position they differ is at the fourth character, and 'c' is smaller than 'd'.
Example 1:
Input: palindrome = "abccba" Output: "aaccba" Explanation: There are many ways to make "abccba" not a palindrome, such as "zbccba", "aaccba", and "abacba". Of all the ways, "aaccba" is the lexicographically smallest.
Example 2:
Input: palindrome = "a" Output: "" Explanation: There is no way to replace a single character to make "a" not a palindrome, so return an empty string.
Constraints:
1 <= palindrome.length <= 1000palindromeconsists of only lowercase English letters.
Approach overview
Problem Overview: You are given a palindromic string and must change exactly one character so the result is not a palindrome. Among all possible results, return the lexicographically smallest string. If no valid change exists (for example, a single-character string), return an empty string.
Approach 1: Try to Replace with 'a' Early (O(n) time, O(1) space)
This greedy approach relies on lexicographic ordering. The smallest character in lowercase strings is 'a', so you try to replace the earliest non-'a' character in the first half of the string with 'a'. Only scanning the first half works because the string is already a palindrome; modifying one side automatically breaks the symmetry. Iterate from index 0 to n/2 and replace the first character that is not 'a'. If every character in that half is already 'a', change the last character to 'b' to guarantee the result is not a palindrome. This greedy rule guarantees the smallest lexicographic result while using constant extra memory. The algorithm runs in O(n) time and O(1) space and uses simple character replacement operations.
This technique fits problems focused on string manipulation where lexicographic order matters. The key insight: breaking the palindrome as early as possible minimizes the resulting string.
Approach 2: Modify Center Character Strategy (O(n) time, O(1) space)
Another way to reason about the problem is to focus on the palindrome's structure. Since the string mirrors around the center, the only safe positions to modify while preserving minimal lexicographic growth are in the left half. Iterate through the string and look for a character that can be reduced lexicographically (for example, changing it to 'a'). If every character in the left half is already minimal, modify the final character to something slightly larger such as 'b'. This guarantees the palindrome property breaks while keeping the result close to the original ordering.
The algorithm still requires a single pass through at most half the string, leading to O(n) time complexity and O(1) space. This approach highlights the greedy decision: always perform the smallest possible change that guarantees the palindrome breaks.
Problems like this frequently appear in greedy algorithms and string categories where the optimal decision can be made locally without backtracking.
Recommended for interviews: The expected interview solution is the greedy scan that replaces the first non-'a' character in the left half. It demonstrates understanding of palindrome symmetry and lexicographic ordering. Brute-force attempts that try every replacement show basic reasoning, but the greedy O(n) solution shows stronger problem-solving and pattern recognition.
Approach 1: Approach 1: Try to Replace with 'a' Early
In this approach, we iterate through the first half of the string and try to replace the first non-'a' character with 'a'. This ensures that we're making the lexicographically smallest change as early as possible in the string. If we can't find a character that is not 'a' in the first half, we replace the last character with 'b' to ensure it's not a palindrome.
def breakPalindrome(palindrome: str) -> str:
if len(palindrome) == 1:
return ""
for i in range(len(palindrome) // 2):
if palindrome[i] != 'a':
return palindrome[:i] + 'a' + palindrome[i+1:]
return palindrome[:-1] + 'b'class Solution {
public String breakPalindrome(String palindrome) {
int len = palindrome.length();
if (len == 1) return "";
char[] chars = palindrome.toCharArray();
for (int i = 0; i < len / 2; ++i) {
if (chars[i] != 'a') {
chars[i] = 'a';
return new String(chars);
}
}
chars[len - 1] = 'b';
return new String(chars);
}
}#include <string>
std::string breakPalindrome(std::string palindrome) {
int len = palindrome.length();
if (len == 1) return "";
for (int i = 0; i < len / 2; ++i) {
if (palindrome[i] != 'a') {
palindrome[i] = 'a';
return palindrome;
}
}
palindrome[len - 1] = 'b';
return palindrome;
}function breakPalindrome(palindrome) {
if (palindrome.length === 1) return "";
let arr = palindrome.split('');
for (let i = 0; i < Math.floor(palindrome.length / 2); i++) {
if (arr[i] !== 'a') {
arr[i] = 'a';
return arr.join('');
}
}
arr[arr.length - 1] = 'b';
return arr.join('');
}#include <string.h>
#include <stdio.h>
char* breakPalindrome(char* palindrome) {
int len = strlen(palindrome);
if (len == 1) return "";
for (int i = 0; i < len / 2; ++i) {
if (palindrome[i] != 'a') {
palindrome[i] = 'a';
return palindrome;
}
}
palindrome[len - 1] = 'b';
return palindrome;
}public class Solution {
public string BreakPalindrome(string palindrome) {
int len = palindrome.Length;
if (len == 1) return "";
char[] chars = palindrome.ToCharArray();
for (int i = 0; i < len / 2; ++i) {
if (chars[i] != 'a') {
chars[i] = 'a';
return new string(chars);
}
}
chars[len - 1] = 'b';
return new string(chars);
}
}In Python, we utilize string slicing to replace the characters, ensuring the smallest lexicographical result.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 2: Approach 2: Modify Center Character
This approach focuses on changing the center character if possible, because altering the center in an odd-length palindrome often results in a non-palindrome quickly. For even lengths, alterations must be controlled to preserve lexicographical order.
def breakPalindrome(palindrome: str) -> str:
if len(palindrome) == 1:
return ""
mid = len(palindrome) // 2
if len(palindrome) % 2 == 1 and palindrome[mid] != 'a':
return palindrome[:mid] + 'a' + palindrome[mid+1:]
for i in range(len(palindrome)):
if palindrome[i] != 'a':
return palindrome[:i] + 'a' + palindrome[i+1:]
return palindrome[:-1] + 'b'class Solution {
public String breakPalindrome(String palindrome) {
int len = palindrome.length();
if (len == 1) return "";
int mid = len / 2;
char[] chars = palindrome.toCharArray();
if (len % 2 == 1 && chars[mid] != 'a') {
chars[mid] = 'a';
return new String(chars);
}
for (int i = 0; i < len; ++i) {
if (chars[i] != 'a') {
chars[i] = 'a';
return new String(chars);
}
}
chars[len - 1] = 'b';
return new String(chars);
}
}#include <string>
std::string breakPalindrome(std::string palindrome) {
int len = palindrome.length();
if (len == 1) return "";
int mid = len / 2;
if (len % 2 == 1 && palindrome[mid] != 'a') {
palindrome[mid] = 'a';
return palindrome;
}
for (int i = 0; i < len; ++i) {
if (palindrome[i] != 'a') {
palindrome[i] = 'a';
return palindrome;
}
}
palindrome[len - 1] = 'b';
return palindrome;
}function breakPalindrome(palindrome) {
if (palindrome.length === 1) return "";
const mid = Math.floor(palindrome.length / 2);
let arr = palindrome.split('');
if (palindrome.length % 2 === 1 && arr[mid] !== 'a') {
arr[mid] = 'a';
return arr.join('');
}
for (let i = 0; i < arr.length; i++) {
if (arr[i] !== 'a') {
arr[i] = 'a';
return arr.join('');
}
}
arr[arr.length - 1] = 'b';
return arr.join('');
}#include <string.h>
#include <stdio.h>
char* breakPalindrome(char* palindrome) {
int len = strlen(palindrome);
if (len == 1) return "";
int mid = len / 2;
if (len % 2 == 1 && palindrome[mid] != 'a') {
palindrome[mid] = 'a';
return palindrome;
}
for (int i = 0; i < len; ++i) {
if (palindrome[i] != 'a') {
palindrome[i] = 'a';
return palindrome;
}
}
palindrome[len - 1] = 'b';
return palindrome;
}public class Solution {
public string BreakPalindrome(string palindrome) {
int len = palindrome.Length;
if (len == 1) return "";
char[] chars = palindrome.ToCharArray();
int mid = len / 2;
if (len % 2 == 1 && chars[mid] != 'a') {
chars[mid] = 'a';
return new string(chars);
}
for (int i = 0; i < len; ++i) {
if (chars[i] != 'a') {
chars[i] = 'a';
return new string(chars);
}
}
chars[len - 1] = 'b';
return new string(chars);
}
}The Python solution prioritizes the center character for modification in odd-length cases, effectively breaking the symmetry.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Greedy
First, we check if the length of the string is 1. If it is, we directly return an empty string.
Otherwise, we traverse the first half of the string from left to right, find the first character that is not 'a', and change it to 'a'. If no such character exists, we change the last character to 'b'.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string.
function breakPalindrome(palindrome: string): string {
const n = palindrome.length;
if (n === 1) {
return '';
}
const s = palindrome.split('');
let i = 0;
while (i < n >> 1 && s[i] === 'a') {
i++;
}
if (i == n >> 1) {
s[n - 1] = 'b';
} else {
s[i] = 'a';
}
return s.join('');
}func breakPalindrome(palindrome string) string {
n := len(palindrome)
if n == 1 {
return ""
}
i := 0
s := []byte(palindrome)
for i < n/2 && s[i] == 'a' {
i++
}
if i == n/2 {
s[n-1] = 'b'
} else {
s[i] = 'a'
}
return string(s)
}impl Solution {
pub fn break_palindrome(palindrome: String) -> String {
let n = palindrome.len();
if n == 1 {
return "".to_string();
}
let mut s: Vec<char> = palindrome.chars().collect();
let mut i = 0;
while i < n / 2 && s[i] == 'a' {
i += 1;
}
if i == n / 2 {
s[n - 1] = 'b';
} else {
s[i] = 'a';
}
s.into_iter().collect()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Try to Replace with 'a' Early | Time Complexity: O(n) |
| Approach 2: Modify Center Character | Time Complexity: O(n) |
| Greedy | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Replace First Non-'a' in Left Half (Greedy) | O(n) | O(1) | Best general solution. Produces the lexicographically smallest valid string with a single scan. |
| Modify Center / Fallback to Last Character | O(n) | O(1) | Alternative greedy reasoning when analyzing palindrome symmetry and minimal character replacements. |
Frequently asked questions
Is Break a Palindrome easy or hard?
Break a Palindrome is classified as a Medium problem on LeetCode. The implementation is short, but identifying the greedy rule—changing the earliest non-'a' character in the left half—requires understanding lexicographic ordering and palindrome symmetry.
Break a Palindrome Python/Java solution
In Python or Java, convert the string to a mutable structure (like a list in Python or a char array in Java). Scan the first half for the first non-'a' character and replace it with 'a'. If none exist, update the last character to 'b'. The implementation runs in O(n) time.
How to solve Break a Palindrome in O(n)?
Iterate through the first half of the palindrome and replace the first character that is not 'a' with 'a'. Because the string is symmetric, modifying one side breaks the palindrome immediately. If all characters are 'a', change the final character to 'b'. This produces the smallest lexicographic result in linear time.
What is the best approach for Break a Palindrome?
The optimal approach is a greedy scan of the first half of the palindrome. Replace the first character that is not 'a' with 'a'. If every character in the first half is already 'a', change the last character to 'b'. This guarantees the lexicographically smallest non-palindrome in O(n) time and O(1) space.
Is Break a Palindrome asked at Google/Amazon/Meta?
Break a Palindrome is a common medium-level string question similar to interview problems asked at companies like Amazon, Google, and Meta. It tests greedy thinking, palindrome properties, and careful handling of edge cases.
What data structure is used in Break a Palindrome?
The problem primarily uses string manipulation with a greedy strategy. No additional data structures are required since the string can be modified directly using character replacement while scanning.
What is the time complexity of Break a Palindrome?
The optimal solution runs in O(n) time because it scans at most half of the string to find a character to modify. Only a constant number of variables are used, so the space complexity is O(1).