| comments | difficulty | edit_url | rating | source | tags | ||
|---|---|---|---|---|---|---|---|
true |
困难 |
2415 |
第 343 场周赛 Q4 |
|
如果一个字符串满足以下条件，则称其为 美丽字符串 ：
- 它由英语小写字母表的前
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是一个美丽字符串
我们可以发现，一个长度为
我们可以贪心地从字符串的最后一个下标开始往前查找，找到一个下标
- 若找到了这样的下标
$i$ ，那么我们将$s[i]$ 替换为$c$ ，并将$s[i+1]$ 到$s[n-1]$ 的字符依次替换为字典序尽可能小的、不与前面相邻两个字符相同的、且在字母表前$k$ 个字符中的字符，替换完成后，我们就得到了一个字典序最小的且大于$s$ 的美丽字符串。 - 若找不到这样的下标
$i$ ，那么我们就无法构造出字典序大于$s$ 的美丽字符串，因此返回空字符串。
时间复杂度
class Solution:
def smallestBeautifulString(self, s: str, k: int) -> str:
n = len(s)
cs = list(s)
for i in range(n - 1, -1, -1):
p = ord(cs[i]) - ord('a') + 1
for j in range(p, k):
c = chr(ord('a') + j)
if (i > 0 and cs[i - 1] == c) or (i > 1 and cs[i - 2] == c):
continue
cs[i] = c
for l in range(i + 1, n):
for m in range(k):
c = chr(ord('a') + m)
if (l > 0 and cs[l - 1] == c) or (l > 1 and cs[l - 2] == c):
continue
cs[l] = c
break
return ''.join(cs)
return ''class Solution {
public String smallestBeautifulString(String s, int k) {
int n = s.length();
char[] cs = s.toCharArray();
for (int i = n - 1; i >= 0; --i) {
int p = cs[i] - 'a' + 1;
for (int j = p; j < k; ++j) {
char c = (char) ('a' + j);
if ((i > 0 && cs[i - 1] == c) || (i > 1 && cs[i - 2] == c)) {
continue;
}
cs[i] = c;
for (int l = i + 1; l < n; ++l) {
for (int m = 0; m < k; ++m) {
c = (char) ('a' + m);
if ((l > 0 && cs[l - 1] == c) || (l > 1 && cs[l - 2] == c)) {
continue;
}
cs[l] = c;
break;
}
}
return String.valueOf(cs);
}
}
return "";
}
}class Solution {
public:
string smallestBeautifulString(string s, int k) {
int n = s.size();
for (int i = n - 1; i >= 0; --i) {
int p = s[i] - 'a' + 1;
for (int j = p; j < k; ++j) {
char c = (char) ('a' + j);
if ((i > 0 && s[i - 1] == c) || (i > 1 && s[i - 2] == c)) {
continue;
}
s[i] = c;
for (int l = i + 1; l < n; ++l) {
for (int m = 0; m < k; ++m) {
c = (char) ('a' + m);
if ((l > 0 && s[l - 1] == c) || (l > 1 && s[l - 2] == c)) {
continue;
}
s[l] = c;
break;
}
}
return s;
}
}
return "";
}
};func smallestBeautifulString(s string, k int) string {
cs := []byte(s)
n := len(cs)
for i := n - 1; i >= 0; i-- {
p := int(cs[i] - 'a' + 1)
for j := p; j < k; j++ {
c := byte('a' + j)
if (i > 0 && cs[i-1] == c) || (i > 1 && cs[i-2] == c) {
continue
}
cs[i] = c
for l := i + 1; l < n; l++ {
for m := 0; m < k; m++ {
c = byte('a' + m)
if (l > 0 && cs[l-1] == c) || (l > 1 && cs[l-2] == c) {
continue
}
cs[l] = c
break
}
}
return string(cs)
}
}
return ""
}function smallestBeautifulString(s: string, k: number): string {
const cs: string[] = s.split('');
const n = cs.length;
for (let i = n - 1; i >= 0; --i) {
const p = cs[i].charCodeAt(0) - 97 + 1;
for (let j = p; j < k; ++j) {
let c = String.fromCharCode(j + 97);
if ((i > 0 && cs[i - 1] === c) || (i > 1 && cs[i - 2] === c)) {
continue;
}
cs[i] = c;
for (let l = i + 1; l < n; ++l) {
for (let m = 0; m < k; ++m) {
c = String.fromCharCode(m + 97);
if ((l > 0 && cs[l - 1] === c) || (l > 1 && cs[l - 2] === c)) {
continue;
}
cs[l] = c;
break;
}
}
return cs.join('');
}
}
return '';
}