题目（难度困难）
如果一个字符串满足以下条件，则称其为美丽字符串 ：
它由英语小写字母表的前 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" 的字符串。
提示
1 <= n == s.length <= 10^5
4 <= k <= 26
s 是一个美丽字符串
字典序概念
字典序，就是按照字典中出现的先后顺序进行排序。
这是单个字符的大小情况，那么如果是两个字符串比较大小呢？在计算机中，两个字符串比较大小，是按照从左到右的顺序进行比较，如果第1位相等，就比较第2位，直至有一位可以比较出大小来，则不再继续比较。
贪心算法
这题难点在于分析题意，如果能知道思路，其实这题不算很难！
长度为2 的回文串就是两个相邻的相同字符，长度为 3的回文串就是下标之差为 2 的两个相同字符。因此，一个字符串是美丽的，当且仅当其中的每个字符与它前面两个字符都不相同。
为了找到比 s 大的，同时又是最小的美丽字符串，我们尝试先从最后一个字符 s[n - 1] 开始修改。因为答案要比 s 大，所以我们只能让 s[n - 1] 变大，且变化后不能和 s[n - 2] 以及 s[n - 3] 相同。
如果我们能在字母表前k 个字符中找到符合要求的字符，那么我们只要修改s[n - 1] 就行了，否则我们还得修改 s[n - 2]。因为答案要比 s 大，所以我们只能让 s[n - 2] 变大，且变化后不能和 s[n - 3] 以及 s[n - 4] 相同。
从上述分析可以看出来，修改每个字符的流程都是一样的：如果我们要修改 s[i]，可以首先枚举字母表的前 k 个字符，看能否找到比 s[i] 大，但又和 s[i - 1] 以及 s[i - 2] 不同的字符。如果找到了即可结束流程，否则我们还得修改 s[i - 1]，重复上述流程。如果已经改到 s[0] 还无法满足要求，那就是无解。
如果修改 s[i] 就能满足要求，由于 s[i] 已经比原来大了，后面的字符不管填什么，答案都会比 s 大。因此 s[i + 1] 到 s[n - 1] 只要贪心地填入与前两个字符不同的最小字符即可。因为 k≥4，我们总能找到这样的字符。
复杂度O(n)。
代码
class Solution {public:string smallestBeautifulString(string s, int k) {int n = s.size();// 这个函数从 s[n - 1] 开始尝试修改，返回最少要修改到哪个位置 + 1auto gao = [&]() {for (int i = n - 1; i >= 0; i--) {// 枚举比 s[i] 大，且是字母表前 k 个的字符for (int j = s[i] + 1; j < k + 'a'; j++) {// 当前字符和前两个字符中的某一个相同，不行if ((i >= 1 && j == s[i - 1]) || (i >= 2 && j == s[i - 2])) continue;// 找到了一个可行字符，修改 s[i]s[i] = j;return i + 1;}}// 改 s[0] 都不行，无解return -1;};int pos = gao(); // 最少修改的位置if (pos == -1) return ""; // 无解// s[pos] 到 s[n - 1] 贪心填入与前两个字符不同的最小字符即可for (int i = pos; i < n; i++) {// 枚举字母表前 k 个字符for (int j = 'a'; j < k + 'a'; j++) {// 当前字符和前两个字符中的某一个相同，不行if ((i >= 1 && j == s[i - 1]) || (i >= 2 && j == s[i - 2])) continue;// 找到了一个可行字符，修改 s[i]，并继续修改下一个字符s[i] = j;break;}}return s;}};
题目链接
https://leetcode.cn/problems/lexicographically-smallest-beautiful-string
参考链接
https://leetcode.cn/problems/lexicographically-smallest-beautiful-string/solution/tan-xin-by-tsreaper-e7ny/
