LC 2182. 构造限制重复的字符串

本文主要是介绍LC 2182. 构造限制重复的字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2182. 构造限制重复的字符串

难度：中等

题目大意：

给你一个字符串 s 和一个整数 repeatLimit ，用 s 中的字符构造一个新字符串 repeatLimitedString ，使任何字母连续出现的次数都不超过 repeatLimit 次。你不必使用 s 中的全部字符。

返回 字典序最大的 repeatLimitedString 。

如果在字符串 a 和 b 不同的第一个位置，字符串 a 中的字母在字母表中出现时间比字符串 b 对应的字母晚，则认为字符串 a 比字符串 b 字典序更大 。如果字符串中前 min(a.length, b.length) 个字符都相同，那么较长的字符串字典序更大。

提示：

1 <= repeatLimit <= s.length <= 105
s 由小写英文字母组成

输入：s = "cczazcc", repeatLimit = 3
输出："zzcccac"
解释：使用 s 中的所有字符来构造 repeatLimitedString "zzcccac"。
字母 'a' 连续出现至多 1 次。
字母 'c' 连续出现至多 3 次。
字母 'z' 连续出现至多 2 次。
因此，没有字母连续出现超过 repeatLimit 次，字符串是一个有效的 repeatLimitedString 。
该字符串是字典序最大的 repeatLimitedString ，所以返回 "zzcccac" 。
注意，尽管 "zzcccca" 字典序更大，但字母 'c' 连续出现超过 3 次，所以它不是一个有效的 repeatLimitedString 。

分析

首先肯定是要思考构造方法，怎么构造呢？先分析要求是什么，字典序最大，也就是说字符串构造出来的字符串要尽量的长，在最长的条件下，尽可能将ASCII码大的放在前面，这里要用到贪心的思想，字典序要尽可能大，我们可以将s从大到小排序，怎么保证合理呢，如果连续的字符的数量没有超过repeatLimit那么就不用管，如果超过了就要用另外一个字符来将这两个字符隔开，怎么选能保证字典序最大呢，当然是选排序后s的第二个不一样的字符了，思路有了，代码用堆来实现，C++中是优先队列

贪心 + 优先队列

class Solution {
public:using PII = pair<char, int>;string repeatLimitedString(string s, int repeatLimit) {int n = s.size();priority_queue<PII> q;unordered_map<char, int> cnt;for (char c : s) cnt[c] ++;for (auto p : cnt) q.push(p);string res;while (q.size()) {auto t = q.top(); q.pop();int x = min(repeatLimit, t.second);res += string(x, t.first);if (q.empty()) break;t.second -= x;if (!t.second) continue;if (x == repeatLimit && q.size()) {auto tt = q.top(); q.pop();res += tt.first;tt.second -= 1;if (tt.second) q.push(tt);}q.push(t);} return res;}
};