Break a Palindrome
Problem
Given a palindromic lowercase string palindrome, replace exactly one character so the result is the lexicographically smallest non-palindrome. Return the new string, or "" if impossible (length 1).
palindrome = "abccba""aaccba"def break_palindrome(p):
n = len(p)
if n < 2: return ""
s = list(p)
for i in range(n // 2):
if s[i] != 'a':
s[i] = 'a'
return "".join(s)
s[-1] = 'b'
return "".join(s)function breakPalindrome(p) {
const n = p.length;
if (n < 2) return "";
const s = p.split("");
for (let i = 0; i < Math.floor(n / 2); i++) {
if (s[i] !== 'a') { s[i] = 'a'; return s.join(""); }
}
s[n - 1] = 'b';
return s.join("");
}class Solution {
public String breakPalindrome(String p) {
int n = p.length();
if (n < 2) return "";
char[] s = p.toCharArray();
for (int i = 0; i < n / 2; i++) {
if (s[i] != 'a') { s[i] = 'a'; return new String(s); }
}
s[n - 1] = 'b';
return new String(s);
}
}string breakPalindrome(string p) {
int n = p.size();
if (n < 2) return "";
for (int i = 0; i < n / 2; i++) {
if (p[i] != 'a') { p[i] = 'a'; return p; }
}
p[n - 1] = 'b';
return p;
}Explanation
We must change exactly one character of a palindrome to make it (a) no longer a palindrome and (b) the lexicographically smallest string possible. To be smallest, we want to shrink an early character as much as we can.
The smallest letter is 'a'. So we scan the left half looking for the first character that is not already 'a'. Changing that to 'a' makes the string smaller and, since its mirror on the right stays unchanged, it can no longer read the same both ways.
Why only the left half? Changing a character in the right half would make the string larger, not smaller, so it is never the best move.
If the whole left half is already all 'a' (like "aaa...a"), we cannot shrink anything. The least-harmful break is to bump the last character up to 'b'. (Length-1 strings are impossible and return "".)
Example: "abccba". The first non-'a' in the left half is the 'b' at index 1, so we flip it to give "aaccba".