1328. Break a Palindrome
Problem Description
The task is to take a palindromic string, which reads the same forwards and backwards, and alter exactly one character to create a new string that is no longer a palindrome. Moreover, the resulting string must be the lexicographically smallest (alphabetically earliest) string possible. Provided that the palindromic string consists of lowercase English letters, if it's impossible to execute such an operation because the string cannot be changed in a way that would not result in a palindrome (for example, if the string is a single character), the function must return an empty string.
Intuition
To solve this problem, we need to understand two key concepts: what makes a string a palindrome and what it means for a string to be lexicographically smaller than another. A palindrome is a string that reads the same forwards as it does backwards. Changing any character in the first half of the string would naturally require a change in the corresponding character in the second half to maintain the property of being a palindrome. To make the resulting string lexicographically smallest, we should aim to replace the first non-'a' character in the string (since 'a' is the smallest letter in the alphabet) with an 'a' if such a character exists in the first half of the string. If the string consists entirely of 'a', any replacement in the first half will still result in a palindrome; therefore, we change the very last character to 'b' (which follows 'a' in the alphabet). The intuition behind changing the last character to 'b' when the string is all 'a's is that we are guaranteed to break the palindrome property while ensuring that the change is minimal and still lexicographically smallest. This strategy leads us to the solution approach where we inspect each character in the first half of the string until we find a non-'a' character to substitute with 'a'. If no such character is found, we overwrite the last character with 'b'.
Learn more about Greedy patterns.
Solution Approach
The solution employs a straightforward iterative approach, with some early returns for edge cases. Specifically, the solution makes use of the following algorithmic steps and simple data structures:
- Convert the input palindromic string,
palindrome
, into a list of characters, stored ins
, to allow mutable operations since strings in Python are immutable. - Determine the length of the input string,
n
, for iterating through its characters. - If
n
equals 1, immediately return an empty string as it's not possible to create a non-palindromic string by changing just one character. This serves as an early exit condition. - Commence a loop to iterate through the first half of the character list
s
, as changing any character in the second half would have a mirrored counterpart in the first half, thus maintaining the palindrome property. - Seek the first occurrence of a character different from
'a'
. If such a character is found at positioni
before reaching the midpoint(n // 2)
, replace it with'a'
to make the string lexicographically smaller while breaking the palindrome. - If the loop finishes without finding any non-'a' characters (meaning the string was composed wholly of 'a's), change the last character in
s
to'b'
. This ensures that the palindrome is broken, and because we are only altering the very end of the string, the outcome remains the lexicographically smallest. - Join the characters in the list
s
back into a string and return it.
This implementation doesn't require complex data structures or patterns; it relies on basic string manipulation and the understanding that a minimal change at the earliest point in a string will lead to the lexicographically smallest outcome.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take the palindromic string abba
as a small example to illustrate the solution approach:
- Convert
abba
into a list of characters,s
, so it becomes['a', 'b', 'b', 'a']
. - The length of
abba
isn = 4
. - Since
n
is greater than 1, we don't return an empty string but proceed with the solution. - We loop through the first half of
s
, which means we only look at the first two characters,['a', 'b']
. - As we start iterating, we find that the first character is an
'a'
and move on to the second character, which is'b'
. - Since
'b'
is different from'a'
, we have found our target character before reaching the midpoint(n // 2)
ofs
, which in this case is at index 1. - We replace the character at index 1 with an
'a'
and nows
becomes['a', 'a', 'b', 'a']
. - We join
s
back into a string, resulting in the non-palindromic stringaaba
, which is lexicographically smaller thanabba
.
In this case, aaba
is returned as the solution since it's the lexicographically smallest string that can be obtained by changing exactly one character in abba
to ensure it's no longer a palindrome.
Solution Implementation
1class Solution:
2 def breakPalindrome(self, palindrome: str) -> str:
3 # Calculate the length of the palindrome string
4 length = len(palindrome)
5
6 # If the length is 1, it is the smallest palindrome and cannot be made non-palindromic
7 if length == 1:
8 return ""
9
10 # Convert the palindrome string into a list of characters for easy manipulation
11 characters = list(palindrome)
12
13 # Initialize an index to iterate over the characters
14 index = 0
15
16 # Iterate over the first half of the palindrome
17 # to find a character that is not 'a'
18 while index < length // 2 and characters[index] == "a":
19 index += 1
20
21 # If all characters in the first half are 'a',
22 # change the last character to 'b' to make it non-palindromic
23 if index == length // 2:
24 characters[-1] = "b"
25 else:
26 # Change the first non-'a' character found in the first half to 'a'
27 characters[index] = "a"
28
29 # Join the characters list to form a new string and return
30 return "".join(characters)
31
32# Example usage:
33# solution = Solution()
34# result = solution.breakPalindrome("abccba") # Returns "aaccba"
35
1class Solution {
2 public String breakPalindrome(String palindrome) {
3 // Get the length of the palindrome string.
4 int length = palindrome.length();
5
6 // If the string is only one character, we cannot make it non-palindrome by changing any letter.
7 if (length == 1) {
8 return "";
9 }
10
11 // Convert the string into a character array for manipulation.
12 char[] charArray = palindrome.toCharArray();
13
14 // initialize an index variable to iterate over the first half of the string.
15 int index = 0;
16
17 // Iterate over the first half of the palindrome.
18 // We only need to check the first half since the second half is a mirror of the first.
19 while (index < length / 2 && charArray[index] == 'a') {
20 // Move to the next character if the current character is 'a'.
21 ++index;
22 }
23
24 // If we've reached the middle without finding a character that is not 'a',
25 // then all characters must be 'a'. In this case, change the last character to 'b'.
26 if (index == length / 2) {
27 charArray[length - 1] = 'b';
28 } else {
29 // Otherwise, we found a non-'a' character in the first half,
30 // change it to 'a' to break the palindrome.
31 charArray[index] = 'a';
32 }
33
34 // Convert the character array back to a string and return the result.
35 return new String(charArray);
36 }
37}
38
1class Solution {
2public:
3 // Break a palindrome by changing the minimum lexicographical character.
4 // The input is guaranteed to be a non-empty palindrome.
5 string breakPalindrome(string palindrome) {
6 int length = palindrome.size();
7
8 // If the palindrome has only one character, it's impossible to make it non-palindromic
9 // by changing any single letter, hence return an empty string.
10 if (length == 1) {
11 return "";
12 }
13
14 // Iterate through the first half of the string
15 for (int i = 0; i < length / 2; ++i) {
16 // If the character is not 'a', change it to 'a' to make the string lexicographically smaller
17 // and ensure it's no longer a palindrome.
18 if (palindrome[i] != 'a') {
19 palindrome[i] = 'a';
20 return palindrome; // The string is no longer a palindrome, return it
21 }
22 }
23
24 // If the loop completes, it means all the characters in the first half are 'a'.
25 // Change the last character to 'b' to make the palindrome lexicographically smallest.
26 palindrome[length - 1] = 'b';
27 return palindrome; // Return the modified palindrome.
28 }
29};
30
1function breakPalindrome(palindrome: string): string {
2 // Get the length of the palindrome
3 const length = palindrome.length;
4
5 // If the string is a single character, it can't be broken into a non-palindrome,
6 // returning an empty string as per the problem statement.
7 if (length === 1) {
8 return '';
9 }
10
11 // Convert the string into an array of characters for easy manipulation.
12 const characters = palindrome.split('');
13
14 // Initialize an index to iterate through the characters of the palindrome.
15 let index = 0;
16
17 // Iterate through the first half of the palindrome searching for a non-'a' character.
18 // If we find an 'a', we increase the index and keep looking
19 // As it's a palindrome, we only need to iterate through the first half of the string.
20 while (index < (length >> 1) && characters[index] === 'a') {
21 index++;
22 }
23
24 // If the whole first half consists of 'a's, it means we have to change the last character
25 // to 'b' because we are looking for the lexicographically smallest palindrome bigger than
26 // the original. All preceding 'a's are the smallest possible characters.
27 if (index == (length >> 1)) {
28 characters[length - 1] = 'b'; // Change the last character to 'b'.
29 } else {
30 characters[index] = 'a'; // Replace the first non-'a' character with 'a'.
31 }
32
33 // Join the array of characters back into a string and return the result.
34 return characters.join('');
35}
36
Time and Space Complexity
Time Complexity
The provided code has a time complexity of O(n)
, where n
is the length of the input string palindrome
. The reason for this time complexity is because the code iterates over at most half of the string (up to n/2
) in the worst-case scenario, in a linear fashion, to find the first non-'a' character. Changing a character and joining the list into a string both require linear time proportional to the length of the string.
Space Complexity
The space complexity is O(n)
as well, because a new list s
of characters is created from the input string, which requires additional space proportional to the size of the input string. The space used by the indices and the temporary storage when changing characters is constant and does not depend on the size of the input, so it does not contribute significantly to the space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!