1047. Remove All Adjacent Duplicates In String (Easy)

Problem

Given a string s, repeatedly remove all adjacent duplicate pairs until no more adjacent duplicates exist. Return the final string.

Adjacent duplicate removal is applied to the entire string simultaneously on each pass (like popping bubbles). The order of removal does not matter: the result is always unique.

Examples

"abbaca" → "ca"
- Remove bb: "aaca"
- Remove aa: "ca"
"azxxzy" → "ay"
- Remove xx: "azzy"
- Remove zz: "ay"

LeetCode 1047 · Link · Easy

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Repeated scanning

Scan the string repeatedly, removing any adjacent duplicate pair on each pass. Stop when no pair is found.

def remove_duplicates(s: str) -> str:
    changed = True
    while changed:                           # L1: up to n/2 passes
        changed = False
        result = []
        i = 0
        while i < len(s):                   # L2: O(n) per pass
            if i + 1 < len(s) and s[i] == s[i + 1]:  # L3: O(1) compare
                i += 2                      # L4: skip the pair
                changed = True
            else:
                result.append(s[i])
                i += 1
        s = "".join(result)                 # L5: O(n) join
    return s

function removeDuplicates(s: string): string {
    let changed = true;
    while (changed) {                                   // L1: up to n/2 passes
        changed = false;
        const result: string[] = [];
        let i = 0;
        while (i < s.length) {                         // L2: O(n) per pass
            if (i + 1 < s.length && s[i] === s[i + 1]) {  // L3: O(1) compare
                i += 2;                                // L4: skip the pair
                changed = true;
            } else {
                result.push(s[i++]);
            }
        }
        s = result.join('');                           // L5: O(n) join
    }
    return s;
}

func removeDuplicates(s string) string {
    changed := true
    for changed {                                      // L1: up to n/2 passes
        changed = false
        result := []byte{}
        i := 0
        for i < len(s) {                              // L2: O(n) per pass
            if i+1 < len(s) && s[i] == s[i+1] {      // L3: O(1) compare
                i += 2                                 // L4: skip the pair
                changed = true
            } else {
                result = append(result, s[i])
                i++
            }
        }
        s = string(result)                             // L5: O(n) join
    }
    return s
}

final class Solution {
    func removeDuplicates(_ s: String) -> String {
        var characters = Array(s)
        var changed = true
        while changed {
            changed = false
            var next: [Character] = []
            var index = 0
            while index < characters.count {
                if index + 1 < characters.count && characters[index] == characters[index + 1] {
                    changed = true
                    index += 2
                } else {
                    next.append(characters[index])
                    index += 1
                }
            }
            characters = next
        }
        return String(characters)
    }
}

Complexity

Time: $O(n²)$ , up to n/2 passes each taking $O(n)$ .
Space: $O(n)$ for result buffer.

Approach 2: Stack cancel (optimal)

Process each character once. If the stack is non-empty and the top equals the current character, they cancel (pop). Otherwise push. The stack accumulates the surviving characters in order.

def remove_duplicates(s: str) -> str:
    stack = []                               # L1: O(1) init
    for ch in s:                             # L2: n iterations
        if stack and stack[-1] == ch:        # L3: O(1) compare top
            stack.pop()                      # L4: O(1) cancel pair
        else:
            stack.append(ch)                 # L5: O(1) no match, push
    return "".join(stack)                    # L6: O(n) join survivors

function removeDuplicates(s: string): string {
    const stack: string[] = [];                                     // L1: O(1) init
    for (const ch of s) {                                           // L2: n iterations
        if (stack.length && stack[stack.length - 1] === ch) {       // L3: O(1) compare top
            stack.pop();                                            // L4: O(1) cancel pair
        } else {
            stack.push(ch);                                         // L5: O(1) no match, push
        }
    }
    return stack.join('');                                          // L6: O(n) join survivors
}

func removeDuplicates(s string) string {
    stack := []byte{}                        // L1: O(1) init
    for i := 0; i < len(s); i++ {           // L2: n iterations
        ch := s[i]
        if len(stack) > 0 && stack[len(stack)-1] == ch { // L3: O(1) compare top
            stack = stack[:len(stack)-1]     // L4: O(1) cancel pair
        } else {
            stack = append(stack, ch)        // L5: O(1) no match, push
        }
    }
    return string(stack)                     // L6: O(n) convert to string
}

final class Solution {
    func removeDuplicates(_ s: String) -> String {
        var stack: [Character] = []
        for character in s {
            if stack.last == character { stack.removeLast() } else { stack.append(character) }
        }
        return String(stack)
    }
}

Where the time goes, line by line

Variables: n = len(s).

Line	Per-call cost	Times executed	Contribution
L2 (loop)	$O(1)$	n	$O(n)$
L3-L5 (compare + push/pop)	$O(1)$	n	$O(n)$ ← dominates
L6 (join)	$O(n)$	1	$O(n)$

Each character is pushed once and popped at most once. Total: $O(n)$ .

Complexity

Time: $O(n)$ , one pass with $O(1)$ per character.
Space: $O(n)$ for the stack (at most n characters survive).

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Why one pass is enough

The multi-pass intuition is that removing one pair might expose a new adjacent pair. The stack handles this automatically: after a pop, the new top of the stack is now adjacent to the next character to process. If they match, the next iteration catches it immediately.

s = "azxxzy"

Push a:  stack = ['a']
Push z:  stack = ['a','z']
Push x:  stack = ['a','z','x']
Push x:  top='x' == 'x', pop.          stack = ['a','z']
Push z:  top='z' == 'z', pop.          stack = ['a']
Push y:  stack = ['a','y']

Result: "ay"

The two z characters only became adjacent after the xx pair was removed. The stack handles this in the same pass because popping xx immediately puts z at the top.

Key takeaways

The stack simulates all cascading removals in a single pass. Each pop is equivalent to one full pass of the naive approach.
The pattern (push; if top equals current, pop instead) appears in several string cancellation problems.
"".join(stack) at the end is $O(n)$ ; calling it inside the loop would make the approach quadratic.
This is the building block for the harder variant (1209. Remove All Adjacent Duplicates in String II), where k-length runs are removed.

Valid Parentheses, stack for matched-pair cancellation
Minimum Remove to Make Valid Parentheses, stack tracks indices for removal
Stacks, underlying data structure

Stack Parsing, the last open, first closed model for nested syntax and reversible operations.
Simulation, the explicit state model for executing rules exactly while keeping cases organized.

1047. Remove All Adjacent Duplicates In String (Easy)

Problem

Try it yourself

Approach 1: Repeated scanning

Approach 2: Stack cancel (optimal)

Why one pass is enough

Key takeaways

Related topics

Related concepts