1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public String breakPalindrome(String palindrome) {
        if (palindrome.length() == 1) {
            return "";
        }
        char[] ans = palindrome.toCharArray();
        int halfLength = palindrome.length() / 2;
        int ptr = 0;
        while (ptr < halfLength && palindrome.charAt(ptr) == 'a') {
            ptr += 1;
        }
        if (ptr == halfLength) {
            ans[ans.length - 1] = 'b';
        } else {
            ans[ptr] = 'a';
        }
        return new String(ans);
    }
}

Greedy. 就是找第一个不是a的位置是哪里. 如果找不到(即都是), 那么最后一个字符变成b即可. 如果找到了, 需要判断是奇数正中间的还是其他情况. 如果是奇数正中间, 我们把它改成a, 这样还是palindrome, 因此此时需要把最后一个字符改成a. 如果不是奇数正中间, 我们把遇到的这个改成a即可.

由于是palindrome, 我们只需要遍历一半即可. 如果我们遍历完发现ptr == halfLength, 不管palindrome是奇数还是偶数长度, 我们都需要把最后一个字符改成b, 因为偶数长度代表着整个string都是a, 奇数长度代表着我们无法通过改变正中间的字符让string变为non-palindrom, 即使正中间可能不是a. 如果遍历完发现ptr < halfLength, 这说明我们找到了一个非a的位置并且不是正中间, 因此把它变为a即可.

时间复杂度: O(n)
空间复杂度: O(n) ans创造了一个数组.