We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Break a Palindrome

Difficulty: Medium

Problem Description

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.

Key Insights

  • A palindrome reads the same forwards and backwards.
  • To break a palindrome, we need to change one character in such a way that the resulting string is not equal to its reverse.
  • The lexicographically smallest string can be obtained by changing the first non-'a' character to 'a', if possible.
  • If the string consists entirely of 'a's, the smallest change would be to change the last character to 'b'.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can utilize a greedy algorithm approach. We'll iterate through the string from the beginning to the middle, looking for the first character that is not 'a'. By changing this character to 'a', we can ensure that the resulting string is lexicographically smaller. If all characters are 'a', we change the last character to 'b'. Additionally, we need to check if the modified string is still a palindrome; if it is not, we return it; otherwise, we return an empty string.

Code Solutions

def breakPalindrome(palindrome: str) -> str:
    n = len(palindrome)
    if n == 1:
        return ""
    
    # Convert to list for mutable string
    s = list(palindrome)
    
    for i in range(n // 2):
        if s[i] != 'a':
            s[i] = 'a'  # Change first non-'a' character to 'a'
            return ''.join(s)
    
    # If all characters are 'a', change the last character to 'b'
    s[-1] = 'b'
    return ''.join(s)
← Back to All Questions