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 <= 1000palindrome consists of only lowercase English letters.The key challenge in #1328 Break a Palindrome is to modify exactly one character in a palindrome so the result becomes non-palindromic while remaining the lexicographically smallest possible string. This naturally leads to a greedy strategy.
Since a palindrome mirrors around its center, only the first half of the string needs careful consideration. To minimize the resulting string lexicographically, the algorithm attempts to replace an early character with a smaller one if possible. If no beneficial replacement exists in the first half (for example when many characters are already minimal), a different adjustment near the end of the string may be required to break the palindrome condition.
Edge cases are important, especially when the string length is 1 or when all characters are already the smallest possible. By scanning the string once and applying this greedy logic, we can efficiently determine the best modification.
This approach runs in O(n) time because we traverse the string once, and uses O(1) extra space since modifications can be done directly on the character array.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy scan of the first half of the string | O(n) | O(1) |
Errichto Algorithms
Use these hints if you're stuck. Try solving on your own first.
How to detect if there is impossible to perform the replacement? Only when the length = 1.
Change the first non 'a' character to 'a'.
What if the string has only 'a'?
Change the last character to 'b'.
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.
Time Complexity: O(n)
Space Complexity: O(1)
1def breakPalindrome(palindrome: str) -> str:
2 if len(palindrome) == 1:
3 return ""
4
5
In Python, we utilize string slicing to replace the characters, ensuring the smallest lexicographical result.
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.
Time Complexity: O(n)
Space Complexity: O(1)
1class
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Break a Palindrome is a common interview-style problem because it tests understanding of greedy logic, string manipulation, and edge-case handling. Similar string transformation questions frequently appear in technical interviews at top tech companies.
The optimal approach uses a greedy strategy. By scanning the first half of the palindrome and attempting the smallest lexicographic modification that breaks symmetry, we can find the answer in a single pass. This ensures minimal changes while keeping the result lexicographically smallest.
The problem mainly relies on string or character array manipulation. By converting the string to a mutable character array, we can modify characters directly while applying a greedy scan.
Because a palindrome mirrors around its center, modifying characters in the first half automatically affects the symmetry of the whole string. Checking the first half is enough to determine whether the palindrome can be broken efficiently.
Similar to other implementations, this Java code modifies the center character for palindromes of odd length.