#   # 1209. Remove All Adjacent Duplicates in String II

## An example of using a std::vector as a std::stack

### Problem statement

You are given a string `s` and an integer `k`, a `k` duplicate removal consists of choosing `k` adjacent and the same 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 is 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 <= 10^5`.

• `2 <= k <= 10^4`.

• `s` only contains lower case English letters.

### Solution: Strings of adjacent equal letters

Construct a stack of strings that has adjacent equal letters and perform the removal during building those strings.

#### Example 2

For `s = "deeedbbcccbdaa"` and `k = 3`:

• The first built string is `"d"`.

• Then `"eee"` with exact length `k`, remove this string.

• The next character is `'d'`, which equals the last character of the last string `"d"`, merge them together. The first string becomes `"dd"`.

• The next string is `"bb"`.

• Then `"ccc"` is removed.

• The next character `'b'` is merged with the last string (`"bb"`) to become `"bbb"` and be removed.

• The next character `'d'` is merged with the last string (`"dd"`) to become `"ddd"` and be removed.

• The remaining string is `"aa"`.

#### Code

``````#include <iostream>
#include <vector>
using namespace std;
string removeDuplicates(string s, int k) {
vector<string> stk;
int i = 0;
while (i < s.length()) {
string a;   // to store adjacent equal letters
// perform the merge
if (!stk.empty() && s[i] == stk.back().back()) {
a = move(stk.back());
stk.pop_back();
}
int j = i;
while (j < s.length() && s[j] == s[i]) {
a += s[j];
// remove the k-duplicate
if (a.length() == k) {
a = "";
}
j++;
}
if (!a.empty()) {
stk.push_back(a);
}
i = j;
}
s = "";
for (auto& str : stk) {
s += str;
}
return s;
}
int main() {
cout << removeDuplicates("abcd", 2) << endl;
cout << removeDuplicates("deeedbbcccbdaa", 3) << endl;
cout << removeDuplicates("pbbcggttciiippooaais", 2) << endl;
}
``````
``````abcd
aa
ps
``````

#### Complexity

• Runtime: `O(N)`, where `N = s.length`.

• Extra space: `O(N)`.

### Implementation notes

The data structure `stk` you might need to solve this problem is a stack. But here are the reasons you had better use `std::vector`:

### References

Thanks for reading! Feel free to share your thought and get my FREE book "10 Classic Coding Challenges".