1328. Break a Palindrome

Break a Palindrome

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.

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.

Idea:

• How to detect if it is impossible to perform the replacement? Only when the length = 1.
• Change the first non 'a' character to 'a'.
• What if the string has only 'a'?
• Change the last character to 'b'.

Code:

/**
 * @param {string} palindrome
 * @return {string}
 */
var breakPalindrome = function (palindrome) {
    const n = palindrome.length;
    if (n === 1) return '';

    for (let i = 0; i < Math.floor(n / 2); i++) {
        if (palindrome[i] !== 'a') {
            return (
                palindrome.substring(0, i) + 'a' + palindrome.substring(i + 1)
            );
        }
    }
    return palindrome.substring(0, n - 1) + 'b';
};

OR

var breakPalindrome = function(palindrome) {
    if (palindrome.length === 1) return "";
    
    for (let i = 0; i < Math.floor(palindrome.length / 2); i++) {
        if (palindrome[i] !== 'a') {
            palindrome = palindrome.replace(palindrome[i], 'a');
            return palindrome;
        }
    }
    
    palindrome = palindrome.substring(0, palindrome.length - 1) + 'b';
    return palindrome;
};

Complexity 

Time Complexity

This problem can be solved with only one loop, so the Time complexity will be O(n).

Space Complexity

one variable needs to be stored so space complexity should also be O(1).

Conclusion

That’s all folks! In this post, we solved LeetCode problem #1328. Break a Palindrome

I hope you have enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.


In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!