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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Break a Palindrome

Number: 1252

Difficulty: Medium

Paid? No

Companies: J.P. Morgan, Oracle, Nvidia, VMware, Expedia

Problem Description

Given a palindromic string of lowercase English letters, replace exactly one character with any lowercase English letter so that the resulting string is not a palindrome, and is the lexicographically smallest one possible. If no such replacement exists, return an empty string.

Key Insights

  • A palindrome is symmetric. Changing a character in the first half affects the symmetry.
  • The lexicographically smallest string is achieved by trying to replace a character with 'a' (except when it already is 'a').
  • For strings with all characters as 'a', changing the last character to 'b' offers the smallest lexicographical option.
  • Edge case: For a single character string, no valid replacement exists.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, since we scan through at most half the string. Space Complexity: O(n) if considering the space for the resulting string, otherwise O(1) extra space.

Solution

The solution uses a greedy approach. First, check if the length of the string is 1 and return an empty string if true. Then, iterate through the first half of the string. For each character, if it is not 'a', replace it with 'a', and return the constructed string immediately as this ensures both that the palindrome property is broken and the string is lexicographically smallest. If no replacement was made in the first half (meaning all characters are 'a'), change the last character to 'b' to break the symmetry.

Code Solutions

def breakPalindrome(palindrome: str) -> str:
    # If the string length is 1, it is impossible to create a non-palindrome
    if len(palindrome) == 1:
        return ""
  
    # Convert the string to a list to modify characters easily
    palindrome_list = list(palindrome)
    n = len(palindrome)
    
    # Loop through the first half of the string
    for i in range(n // 2):
        # If a character is not 'a', change it to 'a' to achieve lexicographical minimality
        if palindrome_list[i] != 'a':
            palindrome_list[i] = 'a'
            return "".join(palindrome_list)
    
    # If all characters in the first half are 'a', change the last character to 'b'
    palindrome_list[-1] = 'b'
    return "".join(palindrome_list)

# Example usage:
# print(breakPalindrome("abccba"))  # Output: "aaccba"
# print(breakPalindrome("a"))       # Output: ""
← Back to All Questions