Remove All Adjacent Duplicates In String

EasyStack · String🧩 Stack LeetCode #1047 ↗Updated Oct 30, 2026

Problem

You have a string s of lowercase letters. A move deletes two neighbouring, equal letters; the pieces on either side then join up and may form a new equal pair. Keep making moves until none is possible and return the final string (it is always unique).

Inputs = "abbaca"Output"ca" (drop "bb" → "aaca", drop "aa" → "ca")

Inputs = "azxxzy"Output"ay"

Inputs = "aa"Output""

1 ≤ s.length ≤ 10⁵ · s consists of lowercase English letters

Try it yourself

Java

class Solution {
    public String removeDuplicates(String s) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A new letter can only cancel with the last surviving letter to its left. Keep the survivors on a stack: if the incoming letter equals the top, pop (they annihilate); otherwise push. One pass does all the chained removals.

PatternStack

Instinct Things resolve in reverse order of arrival (brackets, adjacent pairs, nested expressions) - push now, pop when its partner shows up.

Memory hack Last in, first out - like a pile of plates, you only ever touch the one on top; every closer pops its opener.

Open the Stack guide →

Approaches

Brute ForceRepeated Scan & Delete

Time O(n²)Space O(n)

Literally simulate the moves: scan for any adjacent equal pair, delete it, and restart the scan one position earlier (the deletion may have created a new pair there). Each deletion shifts the rest of the buffer, so up to n/2 deletions cost O(n) each.

Java

public String removeDuplicates(String s) {
    StringBuilder sb = new StringBuilder(s);
    int i = 0;
    while (i + 1 < sb.length()) {
        if (sb.charAt(i) == sb.charAt(i + 1)) {
            sb.delete(i, i + 2);      // O(n) shift
            i = Math.max(0, i - 1);   // a new pair may now touch i-1
        } else {
            i++;
        }
    }
    return sb.toString();
}

Faithful to the statement, but quadratic on inputs like "abccba...".

BetterExplicit Stack of Characters

Time O(n)Space O(n)

Push each character unless it matches the top, in which case pop instead. The stack always holds a duplicate-free survivor string, so a new letter only needs to be compared with the top. Finally read the stack bottom-to-top.

Java

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 sb = new StringBuilder();
    while (!stack.isEmpty()) sb.append(stack.pollLast()); // bottom first
    return sb.toString();
}

Linear, but boxes every char into a Deque and needs a rebuild.

OptimalIn-place Write Pointer (char[] as Stack)

Time O(n)Space O(n)

Use the char array itself as the stack: top is its size, and the stack lives in a[0..top-1]. Since top never passes the read index, writing into the array is safe. The answer is the first top chars — only the output buffer is allocated.

Java

public String removeDuplicates(String s) {
    char[] a = s.toCharArray();
    int top = 0; // a[0..top-1] are the survivors
    for (int i = 0; i < a.length; i++) {
        if (top > 0 && a[top - 1] == a[i]) {
            top--;          // cancel with the last survivor
        } else {
            a[top++] = a[i];
        }
    }
    return new String(a, 0, top);
}

Dry run"abbaca"

t top (next write)i read changed

i=1
a

b
i
b
t
a

c

a

push b, top=2
i=2
a

b
t
b
i
a

c

a

b==b → top=1
i=3
a
t
b

b

a
i
c

a

a==a → top=0
i=4
c

b
t
b

a

c
i
a

write c, top=1
i=5
c

a

b
t
a

c

a
i
write a, top=2
end
c

a

b
t
a

c

a

return "ca" ✔

Same O(n) bound, minimal constant factor — no boxing, no extra stack.

Pro tip

A StringBuilder works the same way: compare with the last char, then deleteCharAt(len-1) or append.

At a glance

Level	Approach	Time	Space
Brute Force	Repeated Scan & Delete	`O(n²)`	`O(n)`
Better	Explicit Stack of Characters	`O(n)`	`O(n)`
Optimal	In-place Write Pointer (char[] as Stack)	`O(n)`	`O(n)`

Common pitfalls

Deleting a pair and continuing from the same index — misses the newly formed pair to the left.
Popping the Deque in push order — returns the survivors reversed.
Assuming a whole run of equal letters vanishes — only pairs cancel, so "aaa" leaves "a".

Interview tips

Notice the removals are like matching brackets — that suggests a stack.
Argue the result is order-independent, so a greedy left-to-right pass is safe.
Offer the char-array version to show you can avoid boxing.

Pattern

Cancel-with-top stack → adjacent elements annihilate or merge, with chain reactions.

My notes saved in this browser