Break a Palindrome
MedPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach systematically generates every possible string that can be formed by changing a single character of the input palindrome. For each generated string, it checks if it's non-palindromic. All such valid strings are collected, and the lexicographically smallest among them is returned.
Algorithm
- Initialize an empty list
candidatesto store valid non-palindromic strings. - Get the length
nof the inputpalindrome. - Handle the edge case: if
n <= 1, it's impossible to make a non-palindrome, so return an empty string"". - Iterate through each character of the palindrome with an index
ifrom0ton-1. - For each position
i, iterate through all possible lowercase characterscfrom 'a' to 'z'. - If the replacement character
cis the same as the original character atpalindrome[i], skip to the next character to avoid making an identical string. - Create a new candidate string
tempby replacing the character at indexiwithc. - Check if
tempis a palindrome. A helper function can be used for this, which compares characters from both ends moving inwards. - If
tempis not a palindrome, add it to thecandidateslist. - After all possible single-character replacements have been generated and checked, find the lexicographically smallest string in the
candidateslist. This can be done by sorting the list and picking the first element. - If the
candidateslist is empty, return"". Otherwise, return the smallest candidate found.
Walkthrough
The brute-force method explores the entire search space of single-character modifications. It iterates through each position in the string and tries substituting every possible lowercase letter. For each substitution that results in a new string, it verifies two conditions: that the new string is not a palindrome and that it was formed by changing exactly one character. All strings that satisfy these conditions are collected. Finally, from this collection of valid outcomes, the one that comes first in lexicographical order is selected as the answer. If no such string can be formed (e.g., for a single-character input), the collection remains empty, and an empty string is returned.
class Solution { public String breakPalindrome(String palindrome) { int n = palindrome.length(); if (n <= 1) { return ""; } java.util.List<String> candidates = new java.util.ArrayList<>(); // Iterate through each position for (int i = 0; i < n; i++) { char originalChar = palindrome.charAt(i); // Try replacing with every lowercase letter for (char c = 'a'; c <= 'z'; c++) { if (c == originalChar) { continue; } char[] arr = palindrome.toCharArray(); arr[i] = c; String temp = new String(arr); if (!isPalindrome(temp)) { candidates.add(temp); } } } if (candidates.isEmpty()) { return ""; } // Find the lexicographically smallest candidate java.util.Collections.sort(candidates); return candidates.get(0); } private boolean isPalindrome(String s) { int left = 0; int right = s.length() - 1; while (left < right) { if (s.charAt(left) != s.charAt(right)) { return false; } left++; right--; } return true; }}Complexity
Time
O(N^2). The outer loop runs N times, and the inner loop runs 26 times. Inside the loops, creating a new string and checking if it's a palindrome both take O(N) time. This results in a total complexity of O(N * 26 * N) which simplifies to O(N^2). Sorting the candidates adds further overhead.
Space
O(N^2), where N is the length of the string. In the worst-case scenario, we might need to store O(N) candidate strings, each of length N.
Trade-offs
Pros
It is a straightforward and easy-to-understand implementation.
It is guaranteed to find the correct solution because it exhaustively checks all possibilities.
Cons
Highly inefficient with a time complexity of O(N^2).
Requires significant space to store all candidate strings, leading to O(N^2) space complexity in the worst case.
Performs many redundant computations, as it doesn't use the properties of palindromes or the lexicographical requirement to prune the search space.
Solutions
Solution
class Solution {public String breakPalindrome(String palindrome) { int n = palindrome.length(); if (n == 1) { return ""; } char[] cs = palindrome.toCharArray(); int i = 0; while (i < n / 2 && cs[i] == 'a') { ++i; } if (i == n / 2) { cs[n - 1] = 'b'; } else { cs[i] = 'a'; } return String.valueOf(cs); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.