Start practising

Remove All Adjacent Duplicates In String

Easy Stack Stack Basics Original on LeetCode

Remove All Adjacent Duplicates In String is a easy stack problem solved with the stack basics pattern. The best approach, optimal (stringbuilder as a stack), runs in O(n) time and O(n) space. Below are 2 approaches in Java, from brute force (repeated scan) up.

Problem

Repeatedly remove two adjacent equal letters from the string until no such pair remains. Return the final string, which is always unique.

Examples

Example 1

Input
s = "abbaca"
Output
"ca"
Why
Remove bb → aaca, then aa → ca.

Example 2

Input
s = "azxxzy"
Output
"ay"

Constraints

  • 1 <= s.length <= 10^5
  • Lowercase letters only.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Brute force (repeated scan)O(n²)O(n)
Optimal (StringBuilder as a stack)O(n)O(n)

1Brute force (repeated scan)

TimeO(n²)
SpaceO(n)

Find the first adjacent equal pair, delete it, and rescan from the start until none is left.

  1. Scan for i with s[i] == s[i+1]; delete both; repeat.
Java
class Solution {
    public String removeDuplicates(String s) {
        StringBuilder sb = new StringBuilder(s);
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int i = 0; i + 1 < sb.length(); i++) {
                if (sb.charAt(i) == sb.charAt(i + 1)) {
                    sb.delete(i, i + 2);
                    changed = true;
                    break;
                }
            }
        }
        return sb.toString();
    }
}

2Optimal (StringBuilder as a stack)

TimeO(n)
SpaceO(n)

Build the result as a stack of kept characters. If the next character equals the top, pop it (the pair cancels); otherwise push it.

  1. For each c: if the last kept char == c, delete it; else append c.
Java
class Solution {
    public String removeDuplicates(String s) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            int n = sb.length();
            if (n > 0 && sb.charAt(n - 1) == c) sb.deleteCharAt(n - 1);
            else sb.append(c);
        }
        return sb.toString();
    }
}

Edge cases to test

  • Everything cancels (empty result)
  • Removals that create new adjacent pairs

Hints

Hint 1

When you read a character, the only thing that matters is the last character still kept.

FAQ

What is the best time complexity for Remove All Adjacent Duplicates In String?

Optimal (StringBuilder as a stack) runs in O(n) time and O(n) extra space.

Which pattern does Remove All Adjacent Duplicates In String use?

It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.

Is there a brute force solution for Remove All Adjacent Duplicates In String?

Yes. Brute force (repeated scan) takes O(n²) time and O(n) space. Find the first adjacent equal pair, delete it, and rescan from the start until none is left.

Which edge cases should I test for Remove All Adjacent Duplicates In String?

Everything cancels (empty result); Removals that create new adjacent pairs.