Sponsored
Sponsored
In this approach, we iterate through the first half of the string and try to replace the first non-'a' character with 'a'. This ensures that we're making the lexicographically smallest change as early as possible in the string. If we can't find a character that is not 'a' in the first half, we replace the last character with 'b' to ensure it's not a palindrome.
Time Complexity: O(n)
Space Complexity: O(1)
1function breakPalindrome(palindrome) {
2 if (palindrome.length === 1) return "";
3
4 let arr = palindrome.split('');
5 for (let i = 0; i < Math.floor(palindrome.length / 2); i++) {
6 if (arr[i] !== 'a') {
7 arr[i] = 'a';
8 return arr.join('');
9 }
10 }
11
12 arr[arr.length - 1] = 'b';
13 return arr.join('');
14}In JavaScript, we split the string into an array for manipulation and join it back into a string after making the necessary change.
This approach focuses on changing the center character if possible, because altering the center in an odd-length palindrome often results in a non-palindrome quickly. For even lengths, alterations must be controlled to preserve lexicographical order.
Time Complexity: O(n)
Space Complexity: O(1)
1#include <string>
std::string breakPalindrome(std::string palindrome) {
int len = palindrome.length();
if (len == 1) return "";
int mid = len / 2;
if (len % 2 == 1 && palindrome[mid] != 'a') {
palindrome[mid] = 'a';
return palindrome;
}
for (int i = 0; i < len; ++i) {
if (palindrome[i] != 'a') {
palindrome[i] = 'a';
return palindrome;
}
}
palindrome[len - 1] = 'b';
return palindrome;
}In C++, this method checks for odd-length palindromes and modifies the middle character when feasible.