Break A Palindrome - Leetcode Solution

The Break a Palindrome problem on Leetcode is a problem that asks the user to modify a given palindrome string in such a way that it is not a palindrome anymore, while at the same time ensuring that the modified string is lexicographically smaller than the original string.

A string is said to be a palindrome if it reads the same both forwards and backwards. For example, “racecar”, “level”, and “madam” are palindromes.

The problem statement involves a string s, and the task is to replace exactly one character of the string s with any lowercase English alphabet so that the resulting string is no longer a palindrome. If the task is not possible, the function should return an empty string. Also, the modified string should be lexicographically smaller than the original string.

To solve this problem, we can use the following approach:

1. Check if the string s is a palindrome or not. If it is a palindrome, we can proceed with the next step, else return the string as it is.
2. If the string s has odd length, we can change any character except for the middle one with ‘a’. Doing so makes the string not a palindrome anymore, and we get the lexicographically smallest string.
3. If the string s has even length, we can go through each character of the string and change the first non-‘a’ character, starting from the beginning of the string. If at any point in the loop, the modified string is not a palindrome anymore, we can stop the loop and return the modified string. If there are no non-‘a’ characters in the string, we can change the last character of the string to ‘b’.

Here is the implementation of the above solution in Python:

class Solution:
    def breakPalindrome(self, s: str) -> str:
        # Check if the string is a palindrome or not
        if len(s) == 1:
            return ""
        elif s == s[::-1]:
            # If the string has odd length, change the middle character to 'a'
            if len(s) % 2 != 0:
                mid = len(s) // 2
                return s[:mid] + 'a' + s[mid + 1:]
            # If the string has even length, change the first non-'a' character
            else:
                for i in range(len(s)):
                    if s[i] != 'a':
                        modified = s[:i] + 'a' + s[i + 1:]
                        if modified != modified[::-1]:
                            return modified
                # If there are no non-'a' characters, change the last character to 'b'
                return s[:-1] + 'b'
        else:
            return s

In this implementation, we first check if the given string is a palindrome or not. If it is a palindrome, we apply the appropriate modifications to the string and return the modified string. If it is not a palindrome, we simply return the original string.

The time complexity of this implementation is O(n), where n is the length of the string s. This is because we need to loop through the string at most twice to modify it, once to check if it is a palindrome or not and once to modify it. The space complexity is O(n) as well, as we are storing the modified string in a new variable.

1