2663. 字典序最小的美丽字符串

如果一个字符串满足以下条件，则称其为 美丽字符串 ：

• 它由英语小写字母表的前 k 个字母组成。
• 它不包含任何长度为 2 或更长的回文子字符串。

给你一个长度为 n 的美丽字符串 s 和一个正整数 k 。

请你找出并返回一个长度为 n 的美丽字符串，该字符串还满足：在字典序大于 s 的所有美丽字符串中字典序最小。如果不存在这样的字符串，则返回一个空字符串。

对于长度相同的两个字符串 a 和 b ，如果字符串 a 在与字符串 b 不同的第一个位置上的字符字典序更大，则字符串 a 的字典序大于字符串 b 。

• 例如，"abcd" 的字典序比 "abcc" 更大，因为在不同的第一个位置（第四个字符）上 d 的字典序大于 c 。

示例 1：

输入：s = "abcz", k = 26

输出："abda"

解释：字符串 "abda" 既是美丽字符串，又满足字典序大于 "abcz" 。 可以证明不存在字符串同时满足字典序大于 "abcz"、美丽字符串、字典序小于 "abda" 这三个条件。

示例 2：

输入：s = "dc", k = 4

输出：""

解释：可以证明，不存在既是美丽字符串，又字典序大于 "dc" 的字符串。

思路：

由于回文串去掉首尾字母后，仍然是回文串，所以长为 m 的回文串必然包含长为 m−2 的回文串。这等价于（逆否命题）如果没有长为 m−2 的回文串，那么也不会有长为 m 的回文串。

根据这一性质，「不包含任何长度为 2 或更长的回文串」等价于「不包含长度为 2 和长度为 3 的回文串」。换句话说，不能出现 s[i]=s[i−1] 以及 s[i]=s[i−2]。

这个性质十分重要，意味着我们只需判断 s[i] 及其左侧的两个字母。

s[i] 及其右侧的两个字母 s[i+1] 和 s[i+2] 呢？交给 i+1 和 i+2 来判断。

既然要字典序最小，那么修改的位置越靠右越好。

下面把 s 视作一个 k 进制数。也就是说，把字母 a 视作 0，字母 b 视作 1，依此类推。

例如 s=dacd, k=4，由于答案要比 s 大，先把末尾的 s[3]=d 加一，进位得到 dada。但这样前三个字母和后三个字母都形成了回文串，我们先来解决前面的，也就是把 s[2]=d 加一，进位得到 dbaa，这样前面就没有回文串了。反过来处理后面的回文串 aa，把 s[3]=a 加一，得到 dbab，还是有回文串，再把 s[3]=b 加一，得到 dbac，这样就没有回文串了。

请注意，题目已经保证输入的 s 是美丽字符串了（不包含回文串），所以一旦发现左侧和右侧都没有回文串，那么就可以返回答案了。

如果计算过程中出现把 s[0] 加一后不在前 k 个字母中的情况，说明答案不存在，返回空字符串。

class Solution {
    public String smallestBeautifulString(String s, int k) {
        k += 'a';
        char[] arr = s.toCharArray();
        int n = s.length();
        int i = n - 1;
        arr[i]++;
        while(i < n){
            if(arr[i] == k){
                arr[i]++;
                if(i == 0){
                    return "";
                }
                arr[i] = 'a';
                arr[--i]++;
            }else if(i > 0 && arr[i] == arr[i - 1] || i > 1 && arr[i] == arr[i - 2]){
                arr[i]++;
            }else{
                i++;
            }
        }
        return new String(arr);
    }
}