以下是 LeetCode 2663“字典序最小的美丽字符串”的 Java 实现。
解题思路
1. 理解“美丽字符串”：
· 长度为 n
· 只包含前 k 个小写字母
· 不包含任何长度大于 1 的回文子串
· 实际上只需检查长度为 2 和 3 的回文（因为更长回文一定包含短回文）
2. 核心要求：
· 找到字典序 大于 s 的最小美丽字符串
· 如果不存在返回空字符串
3. 贪心 + 回溯：
· 从字符串末尾开始尝试增加字符
· 每次增加后检查是否与前面 1 位或 2 位形成回文
· 如果冲突则继续增加，如果无法增加则回退到前一位
Java 代码
```java
class Solution {
public String smallestBeautifulString(String s, int k) {
char[] chars = s.toCharArray();
int n = chars.length;
// 从末尾开始尝试
for (int i = n - 1; i >= 0; i--) {
// 尝试将当前位置字符增加
for (char c = (char)(chars[i] + 1); c < 'a' + k; c++) {
// 检查是否与前面形成回文
if (i > 0 && c == chars[i - 1]) continue;
if (i > 1 && c == chars[i - 2]) continue;
// 找到可行字符
chars[i] = c;
// 将后面的字符填充为最小可行字符
for (int j = i + 1; j < n; j++) {
for (char d = 'a'; d < 'a' + k; d++) {
if (j > 0 && d == chars[j - 1]) continue;
if (j > 1 && d == chars[j - 2]) continue;
chars[j] = d;
break;
}
}
return new String(chars);
}
}
return "";
}
}
```
算法说明
1. 回文检查：
· 只需要检查与前 1 位（长度为 2 的回文）
· 和与前 2 位（长度为 3 的回文）
· 因为更长的回文一定包含这两个中的某一个
2. 贪心策略：
· 从右向左找到第一个可以增加的字符位置
· 将其增加为满足条件的最小字符
· 后续位置全部填充为最小可行字符
3. 字符集限制：
· 只能使用 'a' 到 'a' + k - 1 的字符
示例演示
```java
// 示例 1
s = "abcz", k = 26
// 从末尾 'z' 无法增加
// 前一位 'c' 增加到 'd'，后面填充 'a','b'...
// 结果： "abdab"
// 示例 2
s = "dc", k = 4 // 字符集 {a,b,c,d}
// 从末尾 'c' 无法增加（只能到 'd'，但 'd' 与前一位 'd' 形成回文 "dd"）
// 前一位 'd' 无法增加（超出字符集）
// 返回 ""
```
复杂度分析
· 时间复杂度：O(n * k)，最坏情况需要尝试每个位置的所有字符
· 空间复杂度：O(n)，存储字符数组
优化版本（更清晰的实现）
```java
class Solution {
public String smallestBeautifulString(String s, int k) {
char[] arr = s.toCharArray();
int n = arr.length;
// 从后往前尝试增加
for (int i = n - 1; i >= 0; i--) {
// 尝试当前位置的所有更大字符
for (char ch = (char)(arr[i] + 1); ch < 'a' + k; ch++) {
// 检查是否与前面的字符形成回文
if (i - 1 >= 0 && ch == arr[i - 1]) continue;
if (i - 2 >= 0 && ch == arr[i - 2]) continue;
// 找到可行解，构造后续字符
arr[i] = ch;
// 填充 i 之后的字符
for (int j = i + 1; j < n; j++) {
for (char c = 'a'; c < 'a' + k; c++) {
if (j - 1 >= 0 && c == arr[j - 1]) continue;
if (j - 2 >= 0 && c == arr[j - 2]) continue;
arr[j] = c;
break;
}
}
return new String(arr);
}
}
return "";
}
}
```
这个解法通过贪心 + 回溯，确保找到字典序最小的美丽字符串。
