Break a Palindrome

Problem Statement

In this challenge, you are provided with a palindromic string exclusively composed of lowercase English letters, named palindrome. A palindromic string reads the same forwards and backwards, such as "radar" or "level". Your task is to modify this string by changing exactly one of its characters to any other lowercase English letter. The goal of this modification is twofold:

• The modified string should not be a palindrome anymore, meaning it should not read the same forwards and backwards.
• Among all possible non-palindromic strings that can be formed by changing one letter, the resulting string should be the lexicographically smallest one.

Lexicographical order is similar to how words are ordered in a dictionary. For example, in lexicographical order, "apple" comes before "banana". To be more specific, given two strings of equal length, the comparison is made based on the first differing character; the string with the smaller character at this position is considered smaller.

If it is impossible to create a non-palindromic string by changing just one character, then you should return an empty string as the result.

Examples

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.

Approach and Intuition

1. Begin by checking if the length of the palindrome is 1. If it's indeed one character long, directly return an empty string since there are no possible modifications that can change the string to non-palindromic.
2. Iterate over the first half of the string (since a palindrome reads the same forwards and backwards, examining just the half suffices).
   • The aim is to find the first character (from the start of the string) that is not 'a'. Changing this character to 'a' would typically yield the lexicographically smallest string.
   • If such a character is found, replace it with 'a' and return the modified string.
3. If all characters in the first half of the string are 'a', then to ensure the resulting string is non-palindromic and still as lexicographically small as possible, the optimal approach would be to change the last character (if it's 'a', change it to 'b').
4. In scenarios where both halves consist only of 'a', and changing the second-to-last 'a' to 'b' results in a minor adjustment but essential for guaranteeing non-palindromicity while keeping the string nearly minimal.

This solution leverages the properties of lexicographical order and the inherent symmetry of palindromic strings to achieve the result efficiently, with primary operations being conditional checks and simple character replacements.

Solutions

class Solution {
public:
    string modifyPalindrome(string palStr) {
        int strLen = palStr.length();
        
        if (strLen == 1) {
            return "";
        }
        
        for (int index = 0; index < strLen / 2; index++) {
            if (palStr[index] != 'a') {
                palStr[index] = 'a';
                return palStr;
            }
        }
        
        palStr[strLen - 1] = 'b';
        return palStr;
    }
};

class Solution {
    public String modifyPalindrome(String palStr) {
        int size = palStr.length();
        if (size == 1) {
            return "";
        }
        // Convert the immutable string into a mutable char array
        char[] chars = palStr.toCharArray();
        
        for (int index = 0; index < size / 2; index++) {
            if (chars[index] != 'a') {
                chars[index] = 'a';
                return String.valueOf(chars);
            }
        }
        
        chars[size - 1] = 'b';
        return String.valueOf(chars);
    }
}