Remove All Adjacent Duplicates In String II

Remove All Adjacent Duplicates in String II is a stack problem with counts. Instead of removing only a pair, we remove a run when its length reaches k.

The useful mental model: keep the cleaned prefix on a stack, and store each character with the number of times it appears consecutively at the current right edge.

Problem

Given a string s and an integer k, repeatedly remove k adjacent equal characters.

Return the final string after no more removals can be made.

Examples:

s = "deeedbbcccbdaa", k = 3 -> "aa"
s = "pbbcggttciiippooaais", k = 2 -> "ps"

First Attempt

class CharCount {
    char c;
    int count;

    public CharCount(char c, int count) {
        this.c = c;
        this.count = count;
    }
}

public String removeDuplicates(String s, int k) {
    Deque<CharCount> stack = new ArrayDeque<>();

    for (char c : s.toCharArray()) {
        if (!stack.isEmpty()) {
            if (stack.peek().c == c) {
                if (stack.peek().count == k - 1) {
                    stack.pop();
                } else {
                    stack.peek().count++;
                }
            } else {
                stack.push(new CharCount(c, 1));
            }
        } else {
            stack.push(new CharCount(c, 1));
        }
    }

    StringBuilder res = new StringBuilder();
    for (CharCount item : stack) {
        for (int i = 0; i < item.count; i++) {
            res.append(item.c);
        }
    }

    return res.reverse().toString();
}

This is the right idea. The stack stores compressed runs, so a block like eee is represented as one item: ('e', 3).

What Changed

The core logic can be flattened:

• when the stack top has the same character, increment its count
• if the count becomes k, remove that run
• otherwise, push a new run with count 1

This keeps the behavior the same while making the state transition easier to read.

Final Version

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    private static class CharCount {
        char value;
        int count;

        CharCount(char value, int count) {
            this.value = value;
            this.count = count;
        }
    }

    public String removeDuplicates(String s, int k) {
        Deque<CharCount> stack = new ArrayDeque<>();

        for (char c : s.toCharArray()) {
            if (!stack.isEmpty() && stack.peek().value == c) {
                stack.peek().count++;

                if (stack.peek().count == k) {
                    stack.pop();
                }
            } else {
                stack.push(new CharCount(c, 1));
            }
        }

        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            CharCount current = stack.pop();
            for (int i = 0; i < current.count; i++) {
                result.append(current.value);
            }
        }

        return result.reverse().toString();
    }
}

Walkthrough

Input:

s = "deeedbbcccbdaa"
k = 3

Important moments:

The final answer is:

"aa"

Why Counts Matter

The first version of this problem removes pairs. In this version, the removal threshold is k, so the stack needs to remember how long the current run is.

After a run disappears, the characters on both sides can become adjacent. The stack handles that because the top always represents the right edge of the cleaned prefix.

Alternative With StringBuilder And Counts

Another common version stores the output directly in a StringBuilder and keeps a parallel count array:

class Solution {
    public String removeDuplicates(String s, int k) {
        StringBuilder stack = new StringBuilder();
        int[] counts = new int[s.length()];

        for (char c : s.toCharArray()) {
            stack.append(c);
            int last = stack.length() - 1;

            counts[last] = last > 0 && stack.charAt(last - 1) == c
                    ? counts[last - 1] + 1
                    : 1;

            if (counts[last] == k) {
                stack.delete(stack.length() - k, stack.length());
            }
        }

        return stack.toString();
    }
}

This avoids reversing at the end because the builder keeps the output order directly.

Complexity

Each character is added once and removed at most once.

Takeaways

• Use a stack when removals can make earlier characters become adjacent again.
• Store counts when the cancellation rule depends on run length.
• Pop as soon as the count reaches k.
• StringBuilder can act as the stack when preserving output order is useful.