> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/stacks-and-queues/remove-all-adjacent-duplicates-in-string-ii.md).

# 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.

```java
class Solution {
    class Adjacent {
        char ch;
        int freq;

        public Adjacent(char ch, int freq) {
            this.ch = ch;
            this.freq = freq;
        }
    }

    // Whenever you are using Queue or LinkedList as stack
    // the pop , peek and push operations take place at the front of the list
    public String removeDuplicates(String s, int k) {
        // LinkedList will be more efficient than Stack because Stack has to reallocate
        // when size over capacity
        Deque<Adjacent> stack = new LinkedList<>();

        for (char c : s.toCharArray()) {
            if (!stack.isEmpty() && stack.peek().ch == c)
                stack.peek().freq++;
            else
                stack.push(new Adjacent(c, 1));
            if (stack.peek().freq == k)
                stack.pop();
        }

        // Convert linked list stack to string
        StringBuilder str = new StringBuilder();
        while (stack.size() > 0) {
            Adjacent peek = stack.removeLast();
            for (int i = 0; i < peek.freq; i++)
                str.append(peek.ch);
        }
        return str.toString();
    }
}
```