Break a Palindrome

Medium

Asked by:

112 views

Topics:

StringsGreedy Algorithms

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 <= 1000
palindrome consists of only lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible length of the input palindrome string?
Can the input palindrome string be empty or null?
If the input string consists of only the character 'a', what should the output be?
Are we guaranteed that the input string will always be a valid palindrome consisting only of lowercase English letters?
If multiple modifications result in lexicographically smallest non-palindrome strings, are we free to return any one of them?

Brute Force Solution

Approach

We need to change a palindrome to make it not a palindrome anymore. The brute force method involves trying every possible change to the input and checking if the result is not a palindrome. We make one modification at a time and assess if it results in a non-palindrome string.

Here's how the algorithm would work step-by-step:

Take the original palindrome.
Try changing the first letter to every other possible letter in the alphabet.
For each of these new words, check if it's a palindrome. If it's not, you've found a solution.
If changing the first letter didn't work, try changing the second letter to every other possible letter.
Again, check if each new word is a palindrome. If not, you've found a solution.
Keep doing this for every letter in the word, one at a time. If you find a change that creates a non-palindrome, you're done.
If you've tried changing every letter and nothing worked, then there may be no possible solution.

Code Implementation

def break_palindrome_brute_force(palindrome):
    palindrome_length = len(palindrome)

    for index in range(palindrome_length):
        # Try changing each letter of the palindrome
        for char_code in range(ord('a'), ord('z') + 1):
            new_char = chr(char_code)
            modified_palindrome = list(palindrome)
            modified_palindrome[index] = new_char
            modified_palindrome = "".join(modified_palindrome)

            # Check if the modification resulted in a non-palindrome
            if modified_palindrome != palindrome and modified_palindrome != modified_palindrome[::-1]:
                return modified_palindrome

    # Handle edge case where input is a single character palindrome
    if palindrome_length <= 1:
        return ""

    # If no change resulted in a non-palindrome, it's impossible
    return ""

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n characters in the input string. For each character, it attempts to replace it with every other lowercase letter of the alphabet (a constant, roughly 26). After each replacement, it checks if the modified string is a palindrome, which takes O(n) time. Therefore, within the outer loop that runs n times, there is a palindrome check costing O(n). Thus the total time complexity is O(n * n), simplifying to O(n²).

Space Complexity

O(1) – The provided algorithm modifies the input string in place. The only auxiliary space used is for a few temporary variables, such as the index for iterating through the string, and potentially a temporary character when modifying the string. The amount of extra space remains constant regardless of the size N of the input palindrome. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The goal is to change a palindrome to a non-palindrome with just one change. The trick is to alter the first non-'a' character to an 'a', but we need to handle special cases like very short palindromes.

Here's how the algorithm would work step-by-step:

First, check if the palindrome is very short (like one letter). If so, it's impossible to break, so just say it can't be done.
If it's longer, go through the first half of the palindrome.
Look for the first character that's not an 'a'.
If you find one, change it to an 'a' and you're done. This is the best way to make it not a palindrome.
If all the characters in the first half are 'a's, it means the entire palindrome is either all 'a's or it has 'a's except for the very last letter if it is of odd length.
In that case, change the very last character to a 'b'. This will always break the palindrome.

Code Implementation

def break_palindrome(palindrome_string):
    list_palindrome = list(palindrome_string)
    palindrome_length = len(list_palindrome)

    if palindrome_length <= 1:
        return ""

    for i in range(palindrome_length // 2):
        # Find the first non-'a' character
        if list_palindrome[i] != 'a':

            list_palindrome[i] = 'a'

            return "".join(list_palindrome)

    # If all chars in the first half are 'a'
    # Change the last char to 'b'
    list_palindrome[palindrome_length - 1] = 'b'

    return "".join(list_palindrome)

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through, at most, the first half of the input palindrome string. In the worst case, it needs to examine roughly n/2 characters to find a non-'a' character or determine if the first half contains only 'a's. If the first half is all 'a's, it modifies the last character. Therefore, the time complexity is directly proportional to the length of the input string, n, resulting in O(n).

Space Complexity

O(1) – The provided algorithm modifies the input string in-place. It doesn't create any additional data structures that scale with the input size N, which is the length of the palindrome string. Therefore, the auxiliary space used is constant, consisting of a few variables for iteration and comparison, regardless of the palindrome's length. This results in a space complexity of O(1).

Edge Cases

Case	How to Handle
Empty or null input string	Return an empty string as there is no palindrome to break.
Single character input string (e.g., 'a')	Return an empty string because modifying a single character can never result in a non-palindrome string.
Two character input string (e.g., 'aa')	Change the first character to 'b' resulting in 'ba'.
Input string of all 'a's (e.g., 'aaaa')	Change the first character to 'b', resulting in 'baaa'.
Input string with an odd length and middle character 'a' (e.g., 'aba')	Change the first 'a' to 'b', resulting in 'bba'.
Input string with an odd length and middle character not 'a' (e.g., 'bbb')	Change the first character to 'a' resulting in 'abb'.
Long palindrome string	The solution should iterate through the string only once, so the time complexity is O(n), making it scale efficiently.
Palindrome that can only be broken by changing the last non-'a' character to 'a'	If the first half is all 'a's, change the last character to 'b' or, if the entire string is 'a's, change the last character to 'b'.

Empty or null input string

How to Handle:

Return an empty string as there is no palindrome to break.

Single character input string (e.g., 'a')

How to Handle:

Return an empty string because modifying a single character can never result in a non-palindrome string.

Two character input string (e.g., 'aa')

How to Handle:

Change the first character to 'b' resulting in 'ba'.

Input string of all 'a's (e.g., 'aaaa')

How to Handle:

Change the first character to 'b', resulting in 'baaa'.

Input string with an odd length and middle character 'a' (e.g., 'aba')

How to Handle:

Change the first 'a' to 'b', resulting in 'bba'.

Input string with an odd length and middle character not 'a' (e.g., 'bbb')

How to Handle:

Change the first character to 'a' resulting in 'abb'.

Long palindrome string

How to Handle:

The solution should iterate through the string only once, so the time complexity is O(n), making it scale efficiently.

Palindrome that can only be broken by changing the last non-'a' character to 'a'

How to Handle:

If the first half is all 'a's, change the last character to 'b' or, if the entire string is 'a's, change the last character to 'b'.