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:

1. Convert the input palindromic string, palindrome, into a list of characters, stored in s, to allow mutable operations since strings in Python are immutable.
2. Determine the length of the input string, n, for iterating through its characters.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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.

Example Walkthrough

Let's take the palindromic string abba as a small example to illustrate the solution approach:

1. Convert abba into a list of characters, s, so it becomes ['a', 'b', 'b', 'a'].
2. The length of abba is n = 4.
3. Since n is greater than 1, we don't return an empty string but proceed with the solution.
4. We loop through the first half of s, which means we only look at the first two characters, ['a', 'b'].
5. As we start iterating, we find that the first character is an 'a' and move on to the second character, which is 'b'.
6. 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.
7. We replace the character at index 1 with an 'a' and now s becomes ['a', 'a', 'b', 'a'].
8. 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

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.