# 1209. Remove All Adjacent Duplicates in String II

You are given a string `s` and an integer `k`, a `k` duplicate removal consists of choosing `k` adjacent and equal letters from `s` and removing them, causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make `k` duplicate removals on `s` until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.

Example 1:

``````Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There's nothing to delete.
``````

Example 2:

``````Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"
``````

Example 3:

``````Input: s = "pbbcggttciiippooaais", k = 2
Output: "ps"
``````

Constraints:

• `1 <= s.length <= 105`
• `2 <= k <= 104`
• `s` only contains lower case English letters.

``````class Solution {
public:
string removeDuplicates(string s, int k) {
int i = 0, n = s.size();
vector<int> cnt(n);
for (int j = 0; j < n; ++j, ++i) {
s[i] = s[j];
cnt[i] = (i > 0 && s[i - 1] == s[i]) ? cnt[i - 1] + 1 : 1;
if (cnt[i] == k) i -= k;
}
return s.substr(0, i);
}
};
``````

``````class Solution {
public:
string removeDuplicates(string s, int k) {
string res;
vector<pair<int, char>> st{{0, '#'}};
for (char c : s) {
if (st.back().second != c) {
st.push_back({1, c});
} else if (++st.back().first == k) {
st.pop_back();
}
}
for (auto &a : st) {
res.append(a.first, a.second);
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1209

Remove All Adjacent Duplicates In String

https://leetcode.com/problems/get-equal-substrings-within-budget/