{x}
blog image

Break a Palindrome

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.

Solution Explanation: Break a Palindrome

The problem asks to modify a palindromic string by changing exactly one character to make it non-palindromic, while keeping the lexicographically smallest result.

Approach:

The solution employs a greedy approach. It iterates through the first half of the palindrome. The goal is to find the first character that isn't 'a' and change it to 'a'. This ensures the lexicographical minimum change. If all characters in the first half are 'a', it means the palindrome consists of only 'a's (like "aaaa"). In this case, we change the last character to 'b'.

Algorithm:

  1. Handle Base Case: If the string length is 1, return an empty string as there's no way to break the palindrome.

  2. Iterate and Modify: Iterate through the first half of the string (up to n // 2 where n is the string length).

    • If you find a character that's not 'a', change that character to 'a'. This guarantees the lexicographically smallest change, since 'a' is the smallest character. Then, return the modified string.
    • If the loop completes without finding a character other than 'a', it means the first half consists entirely of 'a's. In this case, change the last character (s[-1]) to 'b'. This creates a non-palindrome while making the minimum change.

  3. Return Result: Return the modified string.

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the string. This is because we iterate through at most half the string in the worst case.
  • Space Complexity: O(n) in the worst case. This is because we create a copy of the input string as a list/array in most of the implementations. In languages where strings are mutable, this could potentially be O(1) extra space.

Code Examples (Python, Java, C++, Go, TypeScript):

The code examples provided earlier demonstrate the algorithm in various programming languages. Each example follows the same logic:

  1. Handles the base case: Checks if the input string length is 1.
  2. Iterates: Iterates through the first half of the string.
  3. Conditional Change: Changes the character based on the condition (non-'a' character found or all 'a's in the first half).
  4. Returns: Returns the modified string.

The differences between the implementations are minor and mainly related to the syntax and data structures of each language. All aim for the same efficient solution.