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)
1class Solution {
2 public String breakPalindrome(String palindrome) {
3 int len = palindrome.length();
4 if (len == 1) return "";
5 char[] chars = palindrome.toCharArray();
6
7 for (int i = 0; i < len / 2; ++i) {
8 if (chars[i] != 'a') {
9 chars[i] = 'a';
10 return new String(chars);
11 }
12 }
13
14 chars[len - 1] = 'b';
15 return new String(chars);
16 }
17}The Java solution uses a character array to efficiently perform the change, similar to other languages, ensuring a lexicographically small non-palindrome.
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#
Focuses on odd-length palindrome to modify the center character, transforming it to 'a' if possible, ensuring not a palindrome.