以下是 LeetCode 2663“字典序最小的美丽字符串”的 Java 实现。解题思路1. 理解“美丽字符串”· 长度为 n· 只包含前 k 个小写字母· 不包含任何长度大于 1 的回文子串· 实际上只需检查长度为 2 和 3 的回文因为更长回文一定包含短回文2. 核心要求· 找到字典序 大于 s 的最小美丽字符串· 如果不存在返回空字符串3. 贪心 回溯· 从字符串末尾开始尝试增加字符· 每次增加后检查是否与前面 1 位或 2 位形成回文· 如果冲突则继续增加如果无法增加则回退到前一位Java 代码javaclass 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// 示例 1s abcz, k 26// 从末尾 z 无法增加// 前一位 c 增加到 d后面填充 a,b...// 结果 abdab// 示例 2s dc, k 4 // 字符集 {a,b,c,d}// 从末尾 c 无法增加只能到 d但 d 与前一位 d 形成回文 dd// 前一位 d 无法增加超出字符集// 返回 复杂度分析· 时间复杂度O(n * k)最坏情况需要尝试每个位置的所有字符· 空间复杂度O(n)存储字符数组优化版本更清晰的实现javaclass 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 ;}}这个解法通过贪心 回溯确保找到字典序最小的美丽字符串。
