REmove adjacent Duplicates in String II

XXX. Remove K Adjacent Duplicates

String

Stack

Problem Statement:

Given a string s and an integer k, remove all groups of k identical consecutive characters and return the resulting string.

• Remove exactly k consecutive identical characters
• Continue the process until no such group exists
• Return final string after all removals

Implementation:

Java Solution:

class Solution {
    class Bucket {
        char c;
        int count;
        Bucket(char c, int count) {
            this.c = c;
            this.count = count;
        }
    }

    public String removeDuplicates(String s, int k) {
        Stack stack = new Stack<>();
        
        // Process each character
        for (char c : s.toCharArray()) {
            if (!stack.isEmpty() && stack.peek().c == c) {
                // Found matching character
                if (stack.peek().count == k - 1)
                    stack.pop();                     // Remove when reaching k
                else
                    stack.peek().count++;           // Increment count
            } else {
                stack.push(new Bucket(c, 1));       // New character
            }
        }
        
        // Build result string
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            Bucket curr = stack.pop();
            for (int i = 0; i < curr.count; i++)
                sb.append(curr.c);
        }
        
        return sb.reverse().toString();             // Reverse to get correct order
    }
}
                

Python Solution:

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stack = []  # Stack of [char, count] pairs
        
        for c in s:
            if stack and stack[-1][0] == c:
                if stack[-1][1] == k - 1:
                    stack.pop()                     # Remove when reaching k
                else:
                    stack[-1][1] += 1               # Increment count
            else:
                stack.append([c, 1])                # New character
        
        # Build result string
        return ''.join(c * count for c, count in stack)
                

C++ Solution:

class Solution {
private:
    struct Bucket {
        char c;
        int count;
        Bucket(char ch, int cnt) : c(ch), count(cnt) {}
    };

public:
    string removeDuplicates(string s, int k) {
        vector stack;  // Use vector as stack
        
        for (char c : s) {
            if (!stack.empty() && stack.back().c == c) {
                if (stack.back().count == k - 1)
                    stack.pop_back();               // Remove when reaching k
                else
                    stack.back().count++;          // Increment count
            } else {
                stack.push_back(Bucket(c, 1));     // New character
            }
        }
        
        // Build result string
        string result;
        for (const Bucket& b : stack)
            result.append(b.count, b.c);           // Append count times char
        
        return result;                             // Already in correct order
    }
};
                

Complexity:

Time Complexity: O(n), where n is string length
Space Complexity: O(n) for stack storage

Explanation:

• **Bucket Structure**:
  • Stores character and its count
  • Enables efficient tracking of duplicates
  • Optimizes space usage
• **Stack Operations**:
  • Push new characters with count 1
  • Increment count for matches
  • Pop when count reaches k
• **Implementation Notes**:
  • Java uses custom Bucket class
  • Python uses list pairs
  • C++ uses struct and vector