Course4all
Join us on telegram
Home/dsa/Stack/Remove All Adjacent Duplicates in String II

Remove All Adjacent Duplicates in String II

Master this topic with zero to advance depth.

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.

← Previous QuestionAsteroid Collision
Next Question →Online Stock Span