stack O(n) time O(n) space
维护一个<字符+频数>的stack 累计连续频数 每次连续频数达到k就出栈 最后把所有字符按频数拼接即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
string removeDuplicates(string s, int k) {
vector<pair<char, int>> stk;
for (char c : s) {
if (stk.empty() || stk.back().first != c) {
stk.emplace_back(c, 1);
} else if (++stk.back().second == k) {
stk.pop_back();
}
}
string res;
for (auto [c, n] : stk) {
res.append(n, c);
}
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
string removeDuplicates(string s, int k) {
vector<pair<char, int>> stk;
for (char c : s) {
if (stk.empty() || stk.back().first != c) {
stk.emplace_back(c, 0);
}
if (++stk.back().second == k) {
stk.pop_back();
}
}
string res;
for (auto [c, n] : stk) {
res.append(n, c);
}
return res;
}
};
|