[LeetCode] Construct String With Repeat Limit

2182. Construct String With Repeat Limit

You are given a string s and an integer repeatLimit. Construct a new string repeatLimitedString using the characters of s such that no letter appears more than repeatLimit times in a row. You do not have to use all characters from s.

Return the lexicographically largest repeatLimitedString possible.

A string a is lexicographically larger than a string b if in the first position where a and b differ, string a has a letter that appears later in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the longer string is the lexicographically larger one.

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
class Solution {
public:
string repeatLimitedString(string s, int repeatLimit) {
map<char, int> count;
for(auto ch : s) count[ch]++;
string ss = "";

while(!count.empty()) {
auto it = prev(count.end());
ss += string(min(repeatLimit, it->second), it->first);
it->second -= min(repeatLimit, it->second);
if(it == count.begin()) break;
auto nxt = prev(it);

if(it->second == 0) {
count.erase(it);
} else {
ss += nxt->first;
nxt->second -= 1;
if(nxt->second == 0)
count.erase(nxt);
}
}

return ss;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/02/20/PS/LeetCode/construct-string-with-repeat-limit/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.