LC 6344. 字典序最小的美丽字符串

https://leetcode.cn/problems/lexicographically-smallest-beautiful-string/

最开始没有啥头绪，看了提示里面一点有点启发

If the string does not contain any palindromic substrings of lengths 2 and 3, then the string does not contain any palindromic substrings at all.

也就是说如果要确保没有任何回文的话，那么只需要保证长度2/3的串没有任何回文。

然后我们可以从最低位开始尝试+1/+2/+3（前提是不存在任何进位），否则不如直接增加高位。一旦在某个位置上可以增加成功的话，然后将剩余位置清零。

假设我们得到了 "abcdeaaaaa", 我们是在e这个位置上+1得到的，问题就是修正之后的aaaaa了，同样我们只需要确保不存在长度2/3的回文串就行。

class Solution:
    def smallestBeautifulString(self, s: str, k: int) -> str:
        CH = [ord(x) - ord('a') for x in s]
        n = len(CH)

        P = -1
        for i in reversed(range(n)):
            a, b, c = CH[i], CH[i - 1] if i - 1 >= 0 else -1, CH[i - 2] if i - 2 >= 0 else -1
            for j in range(1, k):
                a = CH[i] + j
                if a < k and a != b and a != c:
                    CH[i] = a
                    P = i
                    break
                if a >= k: break
            if P != -1: break

        if P == -1: return ""
        # print(CH, ''.join([chr(x + ord('a')) for x in CH]))

        for i in range(P + 1, n):
            a, b = CH[i - 2] if i - 2 >= 0 else -1, CH[i - 1] if i - 1 >= 0 else -1
            for j in range(k):
                if j != a and j != b:
                    CH[i] = j
                    break
        ans = ''.join([chr(x + ord('a')) for x in CH])
        return ans