Break a Palindrome LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Expedia Facebook GoDaddy Goldman Sachs JPMorgan LinkedIn Visa VMware ZillowViews 5178

Problem Statement:

Break a Palindrome LeetCode Solution: 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'.

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.

Approach:

Idea:

The idea is to first traverse the first half of the string and check if we can replace any character of the string with the character ‘a’. If we can, then the resulting string will be our answer. If not, then we will iterate over the later half of the string and will check if we can replace any character with the smallest ASCII character starting from ‘a’ to ‘z’. We are doing this to get the lexicographically smallest string.

This problem may sound difficult but breaking it into several test cases will lead to an easy/intuitive one.

  1. The base case is if the input of 1 length, we can’t break that palindrome then return “”.
  2. Now think how we can break a palindrome and a new string is lexicographically smallest.
    -> If we just find the first non ‘a’ character and replace it with ‘a’
    e.g. abccba
    first non- ‘a’ character is ‘b’ at position 1 (0-indexing)
    Replacing it with ‘a’ will suffice for this scenario — aaccba
  3.  Logic is not over yet, what if the input String contains only ‘a’s?
    ->Does replacing the last character with ‘b’ helps? Bingo!!!
    e.g. aaaa
    Replace the last character with ‘b’ — aaab

Code:

Break a Palindrome C++ Solution:

class Solution {
public:
    string breakPalindrome(string pd) {
        int n=pd.length();
        if(n==1)
            return "";
        if(n%2==0){
            for(int i=0;i<n/2;i++){
                if(pd[i]!='a'){
                    pd[i]='a';
                    return pd;
                }
            }
            for(int j=0;j<26;j++){
                for(int i=n-1;i>=n/2;i--){
                    if(pd[i]!=char('a'+j)){
                        pd[i]=char('a'+j);
                        return pd;
                    }
                }
            }
        }
        else{
            for(int i=0;i<n/2;i++){
                if(pd[i]!='a'){
                    pd[i]='a';
                    return pd;
                }
            }
            for(int j=0;j<26;j++){
                for(int i=n-1;i>n/2;i--){
                    if(pd[i]!=char('a'+j)){
                        pd[i]=char('a'+j);
                        return pd;
                    }
                }
            }
        }
        return "";
    }
};

Complexity Analysis of Break a Palindrome LeetCode Solution:

Translate »