class Solution {
public:
string smallestBeautifulString(string s, int k) {
}
};
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" 的字符串。
提示：
1 <= n == s.length <= 1054 <= k <= 26s 是一个美丽字符串原站题解
cpp 解法, 执行用时: 58 ms, 内存消耗: 19.8 MB, 提交时间: 2024-06-22 09:42:52
class Solution {
public:
string smallestBeautifulString(string s, int k) {
k += 'a';
int n = s.length();
int i = n - 1; // 从最后一个字母开始
s[i]++; // 先加一
while (i < n) {
if (s[i] == k) { // 需要进位
if (i == 0) { // 无法进位
return "";
}
// 进位
s[i] = 'a';
s[--i]++;
} else if (i && s[i] == s[i - 1] || i > 1 && s[i] == s[i - 2]) {
s[i]++; // 如果 s[i] 和左侧的字符形成回文串，就继续增加 s[i]
} else {
i++; // 反过来检查后面是否有回文串
}
}
return s;
}
};
golang 解法, 执行用时: 12 ms, 内存消耗: 6.5 MB, 提交时间: 2023-05-05 17:07:39
func smallestBeautifulString(S string, k int) string {
limit := 'a' + byte(k)
s := []byte(S)
n := len(s)
i := n - 1
s[i]++ // 从最后一个字母开始
for i < n {
if s[i] == limit { // 超过范围
if i == 0 { // 无法进位
return ""
}
// 进位
s[i] = 'a'
i--
s[i]++
} else if i > 0 && s[i] == s[i-1] || i > 1 && s[i] == s[i-2] {
s[i]++ // 如果 s[i] 和前面的字符形成回文串，就继续增加 s[i]
} else {
i++ // 检查 s[i] 是否和后面的字符形成回文串
}
}
return string(s)
}
java 解法, 执行用时: 10 ms, 内存消耗: 43.6 MB, 提交时间: 2023-05-05 17:07:27
class Solution {
public String smallestBeautifulString(String S, int k) {
k += 'a';
var s = S.toCharArray();
int n = s.length, i = n - 1;
++s[i]; // 从最后一个字母开始
while (i < n) {
if (s[i] == k) { // 超过范围
if (i == 0) return ""; // 无法进位
// 进位
s[i] = 'a';
++s[--i];
} else if (i > 0 && s[i] == s[i - 1] || i > 1 && s[i] == s[i - 2]) {
++s[i]; // 如果 s[i] 和前面的字符形成回文串，就继续增加 s[i]
} else {
++i; // 检查 s[i] 是否和后面的字符形成回文串
}
}
return new String(s);
}
}
python3 解法, 执行用时: 344 ms, 内存消耗: 18.5 MB, 提交时间: 2023-05-05 17:07:14
class Solution:
def smallestBeautifulString(self, s: str, k: int) -> str:
a = ord('a')
k += a
s = list(map(ord, s))
n = len(s)
i = n - 1
s[i] += 1 # 从最后一个字母开始
while i < n:
if s[i] == k: # 超过范围
if i == 0: return "" # 无法进位
# 进位
s[i] = a
i -= 1
s[i] += 1
elif i and s[i] == s[i - 1] or i > 1 and s[i] == s[i - 2]:
s[i] += 1 # 如果 s[i] 和前面的字符形成回文串，就继续增加 s[i]
else:
i += 1 # 检查 s[i] 是否和后面的字符形成回文串
return ''.join(map(chr, s))