题目描述
给你一个字符串 s
和一个整数 repeatLimit
,用 s
中的字符构造一个新字符串 repeatLimitedString
,使任何字母 连续 出现的次数都不超过 repeatLimit
次。你不必使用 s
中的全部字符。
返回 字典序最大的 repeatLimitedString
。
如果在字符串 a
和 b
不同的第一个位置,字符串 a
中的字母在字母表中出现时间比字符串 b
对应的字母晚,则认为字符串 a
比字符串 b
字典序更大。如果字符串中前 min(a.length, b.length)
个字符都相同,那么较长的字符串字典序更大。
样例
输入:s = "cczazcc", repeatLimit = 3
输出:"zzcccac"
解释:使用 s 中的所有字符来构造 repeatLimitedString "zzcccac"。
字母 'a' 连续出现至多 1 次。
字母 'c' 连续出现至多 3 次。
字母 'z' 连续出现至多 2 次。
因此,没有字母连续出现超过 repeatLimit 次,字符串是一个有效的 repeatLimitedString。
该字符串是字典序最大的 repeatLimitedString,所以返回 "zzcccac"。
注意,尽管 "zzcccca" 字典序更大,但字母 'c' 连续出现超过 3 次,
所以它不是一个有效的 repeatLimitedString。
输入:s = "aababab", repeatLimit = 2
输出:"bbabaa"
解释:
使用 s 中的一些字符来构造 repeatLimitedString "bbabaa"。
字母 'a' 连续出现至多 2 次。
字母 'b' 连续出现至多 2 次。
因此,没有字母连续出现超过 repeatLimit 次,字符串是一个有效的 repeatLimitedString。
该字符串是字典序最大的 repeatLimitedString,所以返回 "bbabaa"。
注意,尽管 "bbabaaa" 字典序更大,但字母 'a' 连续出现超过 2 次,
所以它不是一个有效的 repeatLimitedString。
限制
1 <= repeatLimit <= s.length <= 10^5
s
由小写英文字母组成。
算法
(贪心,快慢指针) $O(n)$
- 统计出
s
中每个字母的出现次数,记为cnt
数组。 - 尽可能的让字典序最大,就需要尽可能的先放大的字符,大的字符的重复次数过多时,需要插入一个次大的字符,然后继续放最大的字符。以此类推。
- 定义两个指针 $i$ 和 $j$,从 25 开始遍历
cnt
数组。当 $i$ 的字符没有拼完时,需要继续拼接 $i$ 的字符,如果中途重复次数过多,则需要借助 $j$ 的字符填充。如果找不到 $j$,则说明不能继续了,直接结束。
时间复杂度
- 遍历字符串一次,拼接答案一次,且字符集大小为常数,故总时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
private:
void append(string &s, int &n, int tot, char c) {
while (tot--)
s[n++] = c;
}
public:
string repeatLimitedString(string s, int repeatLimit) {
vector<int> cnt(26, 0);
for (char c : s)
cnt[c - 'a']++;
int n = 0;
for (int i = 25, j = 24; i >= 0; i--) {
if (j >= i)
j = i - 1;
while (cnt[i] > 0) {
if (cnt[i] <= repeatLimit) {
append(s, n, cnt[i], i + 'a');
break;
}
append(s, n, repeatLimit, i + 'a');
cnt[i] -= repeatLimit;
while (j >= 0 && cnt[j] == 0)
j--;
if (j < 0)
break;
cnt[j]--;
s[n++] = j + 'a';
}
}
s.resize(n);
return s;
}
};