Problem Description

Given a string s and an integer k, remove all adjacent duplicates in the string where a group of exactly k adjacent, identical characters are found. This process should be repeated as many times as possible until no more such groups exist. The final result should be returned as a string.

• Only groups of exactly k adjacent, identical characters are removed at each step.
• Removal may create new groups that should also be removed in subsequent passes.
• The process continues until no such group exists in the string.
• All removals are done in-place, and the order of characters not removed must be preserved.

Example:
Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: First, remove "eee" and "ccc", then "bbb" becomes "bb", which is not enough, and finally, "aa" remains.

Thought Process

A naive approach would be to scan the string repeatedly, removing groups of k identical adjacent characters until no more can be removed. However, this brute-force method is inefficient, especially for long strings and small k.

To optimize, we need a way to efficiently track consecutive characters and their counts as we process the string. The key observation is that we only care about runs of adjacent, identical characters and their lengths. If we can track both the character and how many times it has appeared consecutively, we can decide when to remove a group in a single pass.

Using a stack is a natural fit: as we process each character, we push it onto the stack along with a count of how many times it has appeared consecutively. When the count reaches k, we pop the group off the stack, effectively removing it from the string.

Solution Approach

We use a stack to keep track of characters and their consecutive counts as we iterate through the string:

1. Initialize an empty stack. Each stack element is a pair: (character, count).
2. Iterate through each character in the string:
• If the stack is not empty and the top of the stack has the same character, increment the count.
• If the count reaches k, pop the top element off the stack (removing the group).
• If the character is different, push (character, 1) onto the stack.
3. After processing all characters, rebuild the string by repeating each character in the stack by its count and concatenating the results.

This approach guarantees that we only need a single pass through the string and maintain at most O(n) space for the stack, where n is the length of the string.

Example Walkthrough

Let's walk through the input s = "deeedbbcccbdaa" with k = 3:

1. Process 'd': stack = [('d', 1)]
2. Process 'e': stack = [('d', 1), ('e', 1)]
3. Process 'e': stack = [('d', 1), ('e', 2)]
4. Process 'e': stack = [('d', 1), ('e', 3)] → count == k, so pop ('e', 3): stack = [('d', 1)]
5. Process 'd': stack = [('d', 2)]
6. Process 'b': stack = [('d', 2), ('b', 1)]
7. Process 'b': stack = [('d', 2), ('b', 2)]
8. Process 'c': stack = [('d', 2), ('b', 2), ('c', 1)]
9. Process 'c': stack = [('d', 2), ('b', 2), ('c', 2)]
10. Process 'c': stack = [('d', 2), ('b', 2), ('c', 3)] → count == k, so pop ('c', 3): stack = [('d', 2), ('b', 2)]
11. Process 'b': stack = [('d', 2), ('b', 3)] → count == k, so pop ('b', 3): stack = [('d', 2)]
12. Process 'd': stack = [('d', 3)] → count == k, so pop ('d', 3): stack = []
13. Process 'a': stack = [('a', 1)]
14. Process 'a': stack = [('a', 2)]

Finally, reconstruct the string: 'aa'.

Time and Space Complexity

• Brute-force approach: Each pass through the string may remove a group, potentially requiring up to O(n) passes. In the worst case, this is O(n^2) time.
• Optimized stack approach: Each character is pushed and popped at most once, so the total time complexity is O(n), where n is the length of s.
• Space complexity: The stack holds at most O(n) characters and counts, so space complexity is O(n).

Code Implementation

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stack = []  # Each element is [char, count]
        for char in s:
            if stack and stack[-1][0] == char:
                stack[-1][1] += 1
                if stack[-1][1] == k:
                    stack.pop()
            else:
                stack.append([char, 1])
        return ''.join(char * count for char, count in stack)
      

class Solution {
public:
    string removeDuplicates(string s, int k) {
        vector

class Solution {
    public String removeDuplicates(String s, int k) {
        Deque<Pair> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (!stack.isEmpty() && stack.peekLast().ch == c) {
                stack.peekLast().count++;
                if (stack.peekLast().count == k) {
                    stack.pollLast();
                }
            } else {
                stack.addLast(new Pair(c, 1));
            }
        }
        StringBuilder sb = new StringBuilder();
        for (Pair p : stack) {
            for (int i = 0; i < p.count; i++) sb.append(p.ch);
        }
        return sb.toString();
    }
    static class Pair {
        char ch;
        int count;
        Pair(char ch, int count) {
            this.ch = ch;
            this.count = count;
        }
    }
}
      

var removeDuplicates = function(s, k) {
    let stack = [];
    for (let char of s) {
        if (stack.length > 0 && stack[stack.length - 1][0] === char) {
            stack[stack.length - 1][1]++;
            if (stack[stack.length - 1][1] === k) {
                stack.pop();
            }
        } else {
            stack.push([char, 1]);
        }
    }
    return stack.map(([char, count]) => char.repeat(count)).join('');
};