题目描述
给你一个字符串 s 和一个整数 repeatLimit ，用 s 中的字符构造一个新字符串 repeatLimitedString ，使任何字母 连续 出现的次数都不超过 repeatLimit 次。你不必使用 s 中的全部字符。
返回 字典序最大的 repeatLimitedString 。
如果在字符串 a 和 b 不同的第一个位置，字符串 a 中的字母在字母表中出现时间比字符串 b 对应的字母晚，则认为字符串 a 比字符串 b 字典序更大 。如果字符串中前 min(a.length, b.length) 个字符都相同，那么较长的字符串字典序更大。
示例 1：
输入：s = "cczazcc", repeatLimit = 3
输出："zzcccac"
解释：使用 s 中的所有字符来构造 repeatLimitedString "zzcccac"。
字母 'a' 连续出现至多 1 次。
字母 'c' 连续出现至多 3 次。
字母 'z' 连续出现至多 2 次。
因此，没有字母连续出现超过 repeatLimit 次，字符串是一个有效的 repeatLimitedString 。
该字符串是字典序最大的 repeatLimitedString ，所以返回 "zzcccac" 。
注意，尽管 "zzcccca" 字典序更大，但字母 'c' 连续出现超过 3 次，所以它不是一个有效的 repeatLimitedString 。
示例 2：
输入：s = "aababab", repeatLimit = 2
输出："bbabaa"
解释：
使用 s 中的一些字符来构造 repeatLimitedString "bbabaa"。
字母 'a' 连续出现至多 2 次。
字母 'b' 连续出现至多 2 次。
因此，没有字母连续出现超过 repeatLimit 次，字符串是一个有效的 repeatLimitedString 。
该字符串是字典序最大的 repeatLimitedString ，所以返回 "bbabaa" 。
注意，尽管 "bbabaaa" 字典序更大，但字母 'a' 连续出现超过 2 次，所以它不是一个有效的 repeatLimitedString 。
提示：
1 <= repeatLimit <= s.length <= 105s 由小写英文字母组成
解法
方法一：贪心
我们先用一个长度为 $26$ 的数组 $cnt$ 统计字符串 $s$ 中每个字符出现的次数，然后从大到小枚举字母表的第 $i$ 个字母，每次取出最多 $\min(cnt[i], repeatLimit)$ 个字母 $i$，如果取完后 $cnt[i]$ 还大于 $0$，则继续取字母表中第 $j$ 个字母，其中 $j$ 是最大的满足 $j < i$ 且 $cnt[j] > 0$ 的下标，直到取完所有字母。
时间复杂度 $O(n + |\Sigma|)$，空间复杂度 $O(|\Sigma|)$。其中 $n$ 是字符串 $s$ 的长度，而 $\Sigma$ 是字符集，本题中 $|\Sigma| = 26$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution:
def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
cnt = [0] * 26
for c in s:
cnt[ord(c) - ord("a")] += 1
ans = []
j = 24
for i in range(25, -1, -1):
j = min(i - 1, j)
while 1:
x = min(repeatLimit, cnt[i])
cnt[i] -= x
ans.append(ascii_lowercase[i] * x)
if cnt[i] == 0:
break
while j >= 0 and cnt[j] == 0:
j -= 1
if j < 0:
break
cnt[j] -= 1
ans.append(ascii_lowercase[j])
return "".join(ans)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | class Solution {
public String repeatLimitedString(String s, int repeatLimit) {
int[] cnt = new int[26];
for (int i = 0; i < s.length(); ++i) {
++cnt[s.charAt(i) - 'a'];
}
StringBuilder ans = new StringBuilder();
for (int i = 25, j = 24; i >= 0; --i) {
j = Math.min(j, i - 1);
while (true) {
for (int k = Math.min(cnt[i], repeatLimit); k > 0; --k) {
ans.append((char) ('a' + i));
--cnt[i];
}
if (cnt[i] == 0) {
break;
}
while (j >= 0 && cnt[j] == 0) {
--j;
}
if (j < 0) {
break;
}
ans.append((char) ('a' + j));
--cnt[j];
}
}
return ans.toString();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | class Solution {
public:
string repeatLimitedString(string s, int repeatLimit) {
int cnt[26]{};
for (char& c : s) {
++cnt[c - 'a'];
}
string ans;
for (int i = 25, j = 24; ~i; --i) {
j = min(j, i - 1);
while (1) {
for (int k = min(cnt[i], repeatLimit); k; --k) {
ans += 'a' + i;
--cnt[i];
}
if (cnt[i] == 0) {
break;
}
while (j >= 0 && cnt[j] == 0) {
--j;
}
if (j < 0) {
break;
}
ans += 'a' + j;
--cnt[j];
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | func repeatLimitedString(s string, repeatLimit int) string {
cnt := [26]int{}
for _, c := range s {
cnt[c-'a']++
}
var ans []byte
for i, j := 25, 24; i >= 0; i-- {
j = min(j, i-1)
for {
for k := min(cnt[i], repeatLimit); k > 0; k-- {
ans = append(ans, byte(i+'a'))
cnt[i]--
}
if cnt[i] == 0 {
break
}
for j >= 0 && cnt[j] == 0 {
j--
}
if j < 0 {
break
}
ans = append(ans, byte(j+'a'))
cnt[j]--
}
}
return string(ans)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | function repeatLimitedString(s: string, repeatLimit: number): string {
const cnt: number[] = Array(26).fill(0);
for (const c of s) {
cnt[c.charCodeAt(0) - 97]++;
}
const ans: string[] = [];
for (let i = 25, j = 24; ~i; --i) {
j = Math.min(j, i - 1);
while (true) {
for (let k = Math.min(cnt[i], repeatLimit); k; --k) {
ans.push(String.fromCharCode(97 + i));
--cnt[i];
}
if (!cnt[i]) {
break;
}
while (j >= 0 && !cnt[j]) {
--j;
}
if (j < 0) {
break;
}
ans.push(String.fromCharCode(97 + j));
--cnt[j];
}
}
return ans.join('');
}
|