Problem statement

Repeatedly remove two adjacent equal letters from s until no such pair remains, and return the final string. The answer is unique regardless of removal order.

Example 1

Input: s = "abbaca"
Output: "ca"
Explanation: "abbaca" → "aaca" → "ca".

Example 2

Input: s = "azxxzy"
Output: "ay"

Constraints

• 1 <= s.length <= 40
• Lowercase English letters.

Hints for Remove All Adjacent Duplicates In String

1. Hint 1

   A stack collapses pairs naturally: pop when the top equals the next char.

2. Hint 2

   The stack content at the end IS the answer.

How to solve Remove All Adjacent Duplicates In String

The awkward part of this problem is the cascade: removing a pair can make two previously separated characters adjacent, which may then collide too. A stack handles that for free, because the character that becomes adjacent after a removal is exactly the one now on top.

Approach

1. Keep a stack of the characters kept so far.
2. For each character of s: if it equals the top of the stack, pop — the pair annihilates.
3. Otherwise push it.
4. Join the stack at the end. It is the answer; no extra passes are needed.

Why it works

The stack always holds the fully reduced version of the prefix scanned so far. Adding one character can only create a collision at the boundary — with the last kept character — and that is the top, which the comparison checks. Popping restores the invariant immediately. The problem also guarantees the result is unique regardless of removal order, so this single left-to-right pass is as valid as any other order.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Repeatedly scanning the string and cutting out pairs is O(n²) and needlessly restarts after every removal.
• After a pop, do not also push the current character — both characters of the pair are gone.
• Check the stack is non-empty before comparing with the top.

Reference solution

Python

def removeDuplicates(s: str) -> str:
    st = []
    for ch in s:
        if st and st[-1] == ch:
            st.pop()
        else:
            st.append(ch)
    return "".join(st)

Java

public static String removeDuplicates(String s) {
    StringBuilder st = new StringBuilder();
    for (char ch : s.toCharArray()) {
        int n = st.length();
        if (n > 0 && st.charAt(n - 1) == ch) st.deleteCharAt(n - 1);
        else st.append(ch);
    }
    return st.toString();
}

C++

string removeDuplicates(string s) {
    string st;
    for (char ch : s) {
        if (!st.empty() && st.back() == ch) st.pop_back();
        else st.push_back(ch);
    }
    return st;
}

JavaScript

var removeDuplicates = function(s) {
    const st = [];
    for (const ch of s) {
        if (st.length > 0 && st[st.length - 1] === ch) st.pop();
        else st.push(ch);
    }
    return st.join("");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Binary Tree Paths Easy
• Find Most Frequent Vowel and Consonant Easy
• Maximum Difference Between Even and Odd Frequency I Easy
• Find Valid Pair of Adjacent Digits in String Easy
• Count the Number of Special Characters I Easy
• Find Maximum Number of String Pairs Easy