Formatted question description: https://leetcode.ca/all/1328.html

# 1328. Break a Palindrome (Medium)

Given a palindromic string palindrome, replace exactly one character by any lowercase English letter so that the string becomes the lexicographically smallest possible string that isn't a palindrome.

After doing so, return the final string.  If there is no way to do so, return the empty string.

Example 1:

Input: palindrome = "abccba"
Output: "aaccba"


Example 2:

Input: palindrome = "a"
Output: ""


Constraints:

• 1 <= palindrome.length <= 1000
• palindrome consists of only lowercase English letters.

Related Topics:
String

## Solution 1.

// OJ: https://leetcode.com/problems/break-a-palindrome/

// Time: O(N)
// Space: O(1)
class Solution {
public:
string breakPalindrome(string palindrome) {
int N = palindrome.size(), end = N / 2;
for (int i = 0; i < end; ++i) {
if (palindrome[i] != 'a') {
palindrome[i] = 'a';
return palindrome;
}
}
if (N > 1) {
palindrome[N - 1] = 'b';
return palindrome;
}
return "";
}
};


Java

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