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)
1def breakPalindrome(palindrome: str) -> str:
2 if len(palindrome) == 1:
3 return ""
4
5 for i in range(len(palindrome) // 2):
6 if palindrome[i] != 'a':
7 return palindrome[:i] + 'a' + palindrome[i+1:]
8
9 return palindrome[:-1] + 'b'In Python, we utilize string slicing to replace the characters, ensuring the smallest lexicographical result.
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)
1public class Solution {
public string BreakPalindrome(string palindrome) {
int len = palindrome.Length;
if (len == 1) return "";
char[] chars = palindrome.ToCharArray();
int mid = len / 2;
if (len % 2 == 1 && chars[mid] != 'a') {
chars[mid] = 'a';
return new string(chars);
}
for (int i = 0; i < len; ++i) {
if (chars[i] != 'a') {
chars[i] = 'a';
return new string(chars);
}
}
chars[len - 1] = 'b';
return new string(chars);
}
}C# relies on a simple mid-point check for odd-length strings, altering as needed.