Course4all

Remove All Adjacent Duplicates in String II

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Stack.

Remove All Adjacent Duplicates in String II

Repeatedly remove k adjacent and equal characters from string s until no more such removals are possible.

Visual Representation

s = "deeedbbcccbdaa", 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=3! Pop (e). 5. Process 'd': Stack [(d, 2)] ... Result: "aa"
Medium

Examples

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Approach 1

Level I: Brute Force (Repeated Removal)

Intuition

Repeatedly scan the string, looking for any group of k consecutive identical characters. When found, remove them and restart the scan. Repeat until no more groups of k are found. This is slow but conceptually simple.
⏱ O(N^2 / k) — Each scan is O(N) and each removal reduces the string by k characters.💾 O(N) for the working string.
java
public class Main {
    public static String removeDuplicates(String s, int k) {
        boolean changed = true;
        while (changed) {
            changed = false;
            int i = 0;
            while (i < s.length()) {
                int j = i;
                while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;
                if (j - i >= k) {
                    s = s.substring(0, i) + s.substring(j);
                    // Trim multiples of k
                    int excess = (j - i) % k;
                    if (excess > 0) {
                        s = s.substring(0, i) + s.charAt(i-1-(j-i-excess)) + s.substring(i);
                    }
                    changed = true;
                    break;
                }
                i++;
            }
        }
        return s;
    }
    public static void main(String[] args) {
        System.out.println(removeDuplicates("deeedbbcccbdaa", 3)); // "aa"
    }
}
Approach 2

Level III: Optimal (Stack of Char-Count Pairs)

Intuition

Use a stack to keep track of characters and their contiguous counts. When the next character matches the top of the stack, increment the top's count. If it matches k, pop it. If it doesn't match, push a new pair (char, 1).
⏱ O(N)💾 O(N)

Detailed Dry Run

CharActionStack (Top Pair)Length
'd'Push(d, 1)1
'e'Push(e, 1)2
'e'Incr(e, 2)2
'e'Pop-1
java
import java.util.*;

public class Solution {
    class Node {
        char c; int count;
        Node(char c, int count) { this.c = c; this.count = count; }
    }
    public String removeDuplicates(String s, int k) {
        Stack<Node> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (!stack.isEmpty() && stack.peek().c == c) {
                stack.peek().count++;
                if (stack.peek().count == k) stack.pop();
            } else stack.push(new Node(c, 1));
        }
        StringBuilder sb = new StringBuilder();
        for (Node node : stack) {
            for (int i = 0; i < node.count; i++) sb.append(node.c);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.removeDuplicates("deeedbbcccbdaa", 3)); // "aa"
    }
}

⚠️ Common Pitfalls & Tips

Ensure the stack stores pairs so you don't have to pop characters one by one. Rebuilding the string efficiently at the end is also key.

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionAsteroid Collision
Next Question →Online Stock Span