Remove All Adjacent Duplicates In String

Remove All Adjacent Duplicates in String is a stack problem. When two equal characters become neighbors, they cancel each other out.

The useful mental model: keep the stable part of the string on a stack. If the next character matches the stack top, remove the top. Otherwise, keep the character.

Problem

Given a string s, repeatedly remove adjacent duplicate characters until no adjacent duplicate pair remains.

Return the final string.

Examples:

"abbaca" -> "ca"
"azxxzy" -> "ay"
"aabb"   -> ""

First Attempt

public String removeDuplicates(String s) {
    Deque<Character> st = new ArrayDeque<>();

    for (char c : s.toCharArray()) {
        if (!st.isEmpty() && st.peek() == c) {
            st.pop();
        } else {
            st.push(c);
        }
    }

    String res = "";
    while (!st.isEmpty()) {
        res = st.pop() + res;
    }

    return res;
}

The stack logic is right.

For each character:

• if it matches the latest kept character, remove that latest character
• otherwise, keep the current character

The main thing to improve is string building. Repeatedly doing res = st.pop() + res creates many temporary strings.

What Changed

Use a StringBuilder for the final output.

Because push adds characters to the front of the deque, the stack pops characters in reverse output order. Append while popping, then reverse once.

Final Version

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

class Solution {
    public String removeDuplicates(String s) {
        Deque<Character> stack = new ArrayDeque<>();

        for (char c : s.toCharArray()) {
            if (!stack.isEmpty() && stack.peek() == c) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }

        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }

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

Walkthrough

Input:

s = "abbaca"

Steps:

Popping gives a, then c, so reverse it to get:

"ca"

Why The Stack Works

Adjacent duplicate removal depends on the latest character that survived.

After a pair disappears, characters that were not previously adjacent may become adjacent. The stack handles that naturally because the top is always the current right edge of the cleaned prefix.

For example:

abbaca

Removing bb makes the two a characters adjacent, so they also disappear.

Alternative With StringBuilder As Stack

For this specific problem, StringBuilder can act as the stack and also avoid the final reverse:

class Solution {
    public String removeDuplicates(String s) {
        StringBuilder stack = new StringBuilder();

        for (char c : s.toCharArray()) {
            int last = stack.length() - 1;
            if (last >= 0 && stack.charAt(last) == c) {
                stack.deleteCharAt(last);
            } else {
                stack.append(c);
            }
        }

        return stack.toString();
    }
}

This is a little tighter because the output order is preserved directly.

Complexity

Each character is pushed once and removed at most once.

Takeaways

• Use a stack when the newest kept item can cancel with the next input item.
• The stack top represents the right edge of the cleaned prefix.
• Avoid repeated string prepending in Java; use StringBuilder.
• A StringBuilder can be used as a stack when the final answer is also a string.