1328. Break a Palindrome

MediumGreedyString

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 in s, 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 position i 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 Evaluator

Example 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 is n = 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) of s, which in this case is at index 1.
We replace the character at index 1 with an 'a' and now s becomes ['a', 'a', 'b', 'a'].
We join s back into a string, resulting in the non-palindromic string aaba, which is lexicographically smaller than abba.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don’t know