题目
如果一个字符串满足以下条件，则称其为 美丽字符串 ：
- 它由英语小写字母表的前 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 是一个美丽字符串
分析
S串是一个美丽字符串，满足规则。
规则解析：
- 要求只能出现前k个小写字母 也就是
0 <= ch - 'a' < k， - 只存在长度>=2的回文串
- 不存在连续两个字符一样的，即：对于位置i的字符不能和
i-1，i+1位置的字符相等，即不存在长度为二的回文字符串 - 对于位置i的字符不能和
i-2，i+2位置的字符相等，即不存在长度为3的回文字符串
- 不存在连续两个字符一样的，即：对于位置i的字符不能和
需要修改原始字符串，使得：
- 得到的新字符串是字典序最小的
- 大小比较规则
- 相同长度，从小到大看每个位置的字典序列，首个较大的字符的字符串是较大串
- 不同长度，如果前序都一样的话，
- 大小比较规则
- 得到的新字符串是美丽字符串
- 字典序列大于原始字符串，那么需要从后往前枚举
贪心
先往左走（增加字典序，处理字典序带来的问题，保证是美丽字符串），再往右走（回溯规则校验）。
算法描述
- 初始化前索引
i = n - 1 - 最后一个字符s[i]++，使得字典序较大
- 循环
i < n，判断每一个位置的s[i]是否满足规则- 如果
s[i]不满足前k个小写字母要求，尝试修改位置靠前的字符- 到达 0 索引，返回无解
- 保证
s[i]是前k个字符，我们操作两个字符s[i-1]++增加左侧字符的字典序s[i] = 'a'重置s[i],保证字典序逐步+1i--下次循环的操作对象
- 如果出现了回文串
- 则当前字符
s[i]字典序+1，然后让s[i]继续进入下一轮循环，因为可能会出现s[i] = k
- 则当前字符
- 否则
- 执行i++，回溯遍历，校验
[i+1,n]是否符合规则
- 执行i++，回溯遍历，校验
- 如果
- 返回字典序最小的、只包含前k个字母的美丽字符串
class Solution {
public String smallestBeautifulString(String S, int k) {
k += 'a';// a及其后面的k-1一个字符。
char[] s = S.toCharArray();
int n = s.length;
int i = n - 1;
// 最后一个字符++，使得比S大
s[i]++;
while(i < n) {
// s[i]的字符大小过大了
if (s[i] == k) {
// 无法解决过大的问题，返回空字符串
if (i == 0) {
return "";
}
s[i-1]++;// 增加下一个字符的字典序列
s[i] = 'a';// 重置成最小的为 a
i--;// 往左移动
} else if (i > 0 && s[i] == s[i - 1] || i > 1 && s[i] == s[i - 2]) {
// 当前变更，会导致后续出现回文串，需要换一个字符，保证是美丽字符串
s[i]++;
} else {
i++;// 满足了美丽和不超过k，需要做一个[i,n]的回归校验。
}
}
return new String(s);
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
