class Solution {
public:
string repeatLimitedString(string s, int repeatLimit) {
}
};
2182. 构造限制重复的字符串
给你一个字符串 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 由小写英文字母组成原站题解
javascript 解法, 执行用时: 112 ms, 内存消耗: 66.6 MB, 提交时间: 2024-01-13 10:57:57
/**
* @param {string} s
* @param {number} repeatLimit
* @return {string}
*/
var repeatLimitedString = function(s, repeatLimit) {
let N = 26;
let count = new Array(N).fill(0);
for (let i = 0; i < s.length; i++) {
count[s.charCodeAt(i) - 97]++;
}
let ret = new Array();
let m = 0;
for (let i = N - 1, j = N - 2; i >= 0 && j >= 0;) {
if (count[i] == 0) { // 当前字符已经填完，填入后面的字符，重置 m
m = 0;
i--;
} else if (m < repeatLimit) { // 当前字符未超过限制
count[i]--;
ret.push(String.fromCharCode(97 + i));
m++;
} else if (j >= i || count[j] == 0) { // 当前字符已经超过限制，查找可填入的其他字符
j--;
} else { // 当前字符已经超过限制，填入其他字符，并且重置 m
count[j]--;
ret.push(String.fromCharCode(97 + j));
m = 0;
}
}
return ret.join('');
};
python3 解法, 执行用时: 300 ms, 内存消耗: 18.8 MB, 提交时间: 2024-01-13 10:57:37
class Solution:
def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
N = 26
count = [0] * N
for c in s:
count[ord(c) - ord('a')] += 1
ret = []
i, j, m = N - 1, N - 2, 0
while i >= 0 and j >= 0:
if count[i] == 0: # 当前字符已经填完，填入后面的字符，重置 m
m, i = 0, i - 1
elif m < repeatLimit: # 当前字符未超过限制
count[i] -= 1
ret.append(chr(ord('a') + i))
m += 1
elif j >= i or count[j] == 0: # 当前字符已经超过限制，查找可填入的其他字符
j -= 1
else: # 当前字符已经超过限制，填入其他字符，并且重置 m
count[j] -= 1
ret.append(chr(ord('a') + j))
m = 0
return ''.join(ret)
java 解法, 执行用时: 19 ms, 内存消耗: 44.4 MB, 提交时间: 2024-01-13 10:57:15
class Solution {
static public int N = 26;
public String repeatLimitedString(String s, int repeatLimit) {
int[] count = new int[N];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
}
StringBuilder ret = new StringBuilder();
int m = 0;
for (int i = N - 1, j = N - 2; i >= 0 && j >= 0;) {
if (count[i] == 0) { // 当前字符已经填完，填入后面的字符，重置 m
m = 0;
i--;
} else if (m < repeatLimit) { // 当前字符未超过限制
count[i]--;
ret.append((char)('a' + i));
m++;
} else if (j >= i || count[j] == 0) { // 当前字符已经超过限制，查找可填入的其他字符
j--;
} else { // 当前字符已经超过限制，填入其他字符，并且重置 m
count[j]--;
ret.append((char)('a' + j));
m = 0;
}
}
return ret.toString();
}
}
cpp 解法, 执行用时: 84 ms, 内存消耗: 24.6 MB, 提交时间: 2024-01-13 10:56:57
const int N = 26;
class Solution {
public:
string repeatLimitedString(string s, int repeatLimit) {
vector<int> count(N);
for (char c : s) {
count[c - 'a']++;
}
string ret;
int m = 0;
for (int i = N - 1, j = N - 2; i >= 0 && j >= 0;) {
if (count[i] == 0) { // 当前字符已经填完，填入后面的字符，重置 m
m = 0;
i--;
} else if (m < repeatLimit) { // 当前字符未超过限制
count[i]--;
ret.push_back('a' + i);
m++;
} else if (j >= i || count[j] == 0) { // 当前字符已经超过限制，查找可填入的其他字符
j--;
} else { // 当前字符已经超过限制，填入其他字符，并且重置 m
count[j]--;
ret.push_back('a' + j);
m = 0;
}
}
return ret;
}
};
golang 解法, 执行用时: 20 ms, 内存消耗: 7.1 MB, 提交时间: 2023-09-19 16:41:59
// use goto label
func repeatLimitedString2(s string, repeatLimit int) string {
cnt := [26]int{}
for _, b := range s {
cnt[b-'a']++
}
ans := []byte{}
for i := 25; i >= 0; i-- { // 从大到小填字母
next:
for j := 0; j < repeatLimit && cnt[i] > 0; j++ { // 填充 min(repeatLimit, cnt[i]) 个字母 i
cnt[i]--
ans = append(ans, 'a'+byte(i))
}
if cnt[i] == 0 { // i 用完了，找下一个更小的字母
continue
}
for j := i - 1; j >= 0; j-- { // i 没用完，插入一个字母 j，这样可以继续填 i
if cnt[j] > 0 {
cnt[j]--
ans = append(ans, 'a'+byte(j))
goto next
}
}
}
return string(ans)
}
// without goto label
func repeatLimitedString(s string, repeatLimit int) string {
cnt := [26]int{}
for _, b := range s {
cnt[b-'a']++
}
ans := []byte{}
for i := 25; i >= 0; i-- { // 从大到小填字母
k := i - 1
for {
for j := 0; j < repeatLimit && cnt[i] > 0; j++ { // 填充 min(repeatLimit, cnt[i]) 个字母 i
cnt[i]--
ans = append(ans, 'a'+byte(i))
}
if cnt[i] == 0 { // i 用完了，找下一个更小的字母
break
}
for k >= 0 && cnt[k] == 0 {
k--
}
if k < 0 {
break
}
// i 没用完，插入一个字母 k，这样可以继续填 i
cnt[k]--
ans = append(ans, 'a'+byte(k))
}
}
return string(ans)
}