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.

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();
    }
}