1.题目（1680）原题链接
给你一个字符串 \(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 <= 10^5\)
- \(s\) 由小写英文字母组成
2.解题思路
从 \(z\) 到 \(a\) 考虑，统计每个字符的出现次数，如果此时 最大字符 的出现次数小于 \(repeatLimit\),则可以直接加入到答案中，大于时，则每隔 \(repeatLimit\) 个字符就要插入一个 次大字符，直到 最大字符 的个数小于 \(repeatLimit\) ，如果此时没有次大字符则直接添加 \(repeatLimit\) 个最大字符到答案中返回答案。用 优先队列(大根堆) 存储字符以及字符出现次数模拟即可。
3.c++代码
class Solution {
public:
string repeatLimitedString(string s, int repeatLimit) {
vector<int> cnt(26,0);
for(char ch:s) cnt[ch-'a']++;
priority_queue<pair<char,int>,vector<pair<char,int>>,less<>> pq;
for(int i=0;i<26;i++){
if(cnt[i]!=0) pq.push(make_pair('a'+i,cnt[i]));
}
string ans;
while(!pq.empty()){
auto q=pq.top();//最大字符
pq.pop();
if(q.second<=repeatLimit){//最大字符出现次数小于repeatLimit直接加入答案
for(int i=0;i<q.second;i++) ans+=q.first;
}else{
if(!pq.empty()){//有次大字符
auto t=pq.top();
pq.pop();
for(int i=0;i<repeatLimit;i++) ans+=q.first;
ans+=t.first;//添加一个次大字符
if(t.second!=1) pq.push(make_pair(t.first,t.second-1));//次大字符有剩余重新入队
pq.push(make_pair(q.first,q.second-repeatLimit));//最大字符肯定有剩余重新入队
}else{//没有次大字符了，直接加repeatLimit个字符返回答案
for(int i=0;i<repeatLimit;i++) ans+=q.first;
return ans;
}
}
}
return ans;
}
};
4.复杂度分析
- 时间复杂度：\(O(n+\Sigma)\)，\(n\) 为字符串长度，\(\Sigma\)为字符集即 \(26\)。
- 空间复杂度：\(O(\Sigma)\)。