Break a Palindrome

Medium
1215.

Break a Palindrome

Break a Palindrome is a medium coding problem on strings and greedy, asked in Amazon, Microsoft and Meta interviews.

You are given a palindrome of lowercase English letters. Replace exactly one of its characters with a different lowercase letter so that the result is not a palindrome, and among all such results return the lexicographically smallest one.

If no replacement can break the palindrome, return an empty string.

Example 1

Input
palindrome = "kayak"
Output
aayak
Explanation
Turning the first `k` into `a` breaks the symmetry and is as small as possible.

Example 2

Input
palindrome = "aba"
Output
abb
Explanation
The first half is already all `a`; changing the middle keeps a palindrome, so the last letter becomes `b`.

Example 3

Input
palindrome = "z"
Output
""
Explanation
Every single letter is a palindrome.

Constraints

  • 1 <= palindrome.length <= 1000
  • palindrome consists of lowercase English letters
  • palindrome reads the same forwards and backwards
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} palindrome
 * @return {string}
 */
var breakPalindrome = function(palindrome) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Break a Palindrome — Solution in Python, Java & C++

Break a Palindrome solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on strings and greedy.

Break a Palindrome is a medium coding problem on strings and greedy, asked in Amazon, Microsoft and Meta interviews.

  • Difficulty: Medium
  • Topics: Strings, Greedy
  • Asked at: Amazon, Microsoft, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a palindrome of lowercase English letters. Replace exactly one of its characters with a different lowercase letter so that the result is not a palindrome, and among all such results return the lexicographically smallest one.

If no replacement can break the palindrome, return an empty string.

Example 1

Input: palindrome = "kayak"
Output: aayak
Explanation: Turning the first `k` into `a` breaks the symmetry and is as small as possible.

Example 2

Input: palindrome = "aba"
Output: abb
Explanation: The first half is already all `a`; changing the middle keeps a palindrome, so the last letter becomes `b`.

Example 3

Input: palindrome = "z"
Output: ""
Explanation: Every single letter is a palindrome.

Constraints

  • 1 <= palindrome.length <= 1000
  • palindrome consists of lowercase English letters
  • palindrome reads the same forwards and backwards

Hints for Break a Palindrome

  1. Hint 1

    A one-letter string can never stop being a palindrome.

  2. Hint 2

    To make the string as small as possible, lower the earliest letter you can — to a.

  3. Hint 3

    Only the first half matters (changing the middle of an odd-length string keeps it a palindrome). If the first half is all a, the best you can do is change the last letter to b.

How to solve Break a Palindrome

The smallest result comes from writing an a as early as possible; if that is impossible without keeping the string a palindrome, the least damaging change is to raise the very last letter to b.

Approach

  1. If the length is 1, return the empty string.
  2. Scan i from 0 while i < n / 2 (the first half, excluding a middle letter). At the first palindrome[i] != 'a', set it to 'a' and return.
  3. Otherwise every letter outside the middle is a: set the last letter to 'b' and return.

Why it works

Changing position i in the first half breaks the symmetry with its mirror n − 1 − i, so the result is not a palindrome; making it a at the earliest such position gives the smallest possible string, since any change at an earlier position would have to raise an a. Changing the middle letter of an odd-length string keeps it a palindrome. If the first half is all a, any change must raise some letter, and raising the last one to b keeps the longest possible prefix of as, so it is the smallest.

Complexity

  • Time — O(n)
  • Space — O(n) for the copy

Pitfalls

  • Changing the middle character of an odd-length palindrome does not break it (aba → aaa).
  • aaaa must become aaab, not baaa.
  • Length 1 has no answer — return an empty string.

Reference solution

Python

def breakPalindrome(palindrome: str) -> str:
    n = len(palindrome)
    if n == 1:
        return ""
    chars = list(palindrome)
    for i in range(n // 2):
        if chars[i] != "a":
            chars[i] = "a"
            return "".join(chars)
    chars[-1] = "b"
    return "".join(chars)

Java

public static String breakPalindrome(String palindrome) {
    int n = palindrome.length();
    if (n == 1) return "";
    char[] chars = palindrome.toCharArray();
    for (int i = 0; i < n / 2; i++) {
        if (chars[i] != 'a') {
            chars[i] = 'a';
            return new String(chars);
        }
    }
    chars[n - 1] = 'b';
    return new String(chars);
}

C++

string breakPalindrome(string palindrome) {
    int n = (int)palindrome.size();
    if (n == 1) return "";
    for (int i = 0; i < n / 2; i++) {
        if (palindrome[i] != 'a') {
            palindrome[i] = 'a';
            return palindrome;
        }
    }
    palindrome[n - 1] = 'b';
    return palindrome;
}

JavaScript

var breakPalindrome = function(palindrome) {
    var n = palindrome.length;
    if (n === 1) return "";
    for (var 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";
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms