1209. Remove All Adjacent Duplicates in String II

Given a string `s`, 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 <= 10^5`
• `2 <= k <= 10^4`
• `s` only contains lower case English letters.

1209. Remove All Adjacent Duplicates in String II
``````struct Solution;

impl Solution {
fn remove_duplicates(s: String, k: i32) -> String {
let mut stack: Vec<(char, usize)> = vec![];
for c in s.chars() {
if let Some(top) = stack.pop() {
if top.0 != c {
stack.push(top);
stack.push((c, 1));
} else {
if (top.1 + 1) != k as usize {
stack.push((c, top.1 + 1));
}
}
} else {
stack.push((c, 1));
}
}
let mut res = "".to_string();
for p in stack {
for _ in 0..p.1 {
res.push(p.0);
}
}
res
}
}

#[test]
fn test() {
let s = "abcd".to_string();
let k = 2;
let res = "abcd".to_string();
assert_eq!(Solution::remove_duplicates(s, k), res);
let s = "deeedbbcccbdaa".to_string();
let k = 3;
let res = "aa".to_string();
assert_eq!(Solution::remove_duplicates(s, k), res);
let s = "pbbcggttciiippooaais".to_string();
let k = 2;
let res = "ps".to_string();
assert_eq!(Solution::remove_duplicates(s, k), res);
}
``````