Break a Palindrome - Solution & Explanation
Problem Statement
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.
This C code checks each character in the first half of the string and replaces the first non-'a' character with 'a'. If no such character is found, it makes the last character 'b'.
Complexity
Time Complexity: O(n)
Space Complexity: O(1)
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.
Focuses on odd-length palindrome to modify the center character, transforming it to 'a' if possible, ensuring not a palindrome.
Complexity
Time Complexity: O(n)
Space Complexity: O(1)
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.
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 | — |
Detailed 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. |
Video Solution
Leetcode problem Break a Palindrome • Errichto Algorithms • 39,815 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Break a Palindrome easy or hard?
Break a Palindrome Python/Java solution
How to solve Break a Palindrome in O(n)?
What is the best approach for Break a Palindrome?
Is Break a Palindrome asked at Google/Amazon/Meta?
What data structure is used in Break a Palindrome?
What is the time complexity of Break a Palindrome?
Ready to solve this problem?
Practice Break a Palindrome with our built-in code editor and test cases.
Practice on FleetCode