Remove Adjacent Duplicate Letters

Problem

Repeatedly remove two adjacent equal letters from the string until no more can be removed. Return the final string.

Constraints

• 1 ≤ s.length ≤ 10⁵

Approach — Stack

This is a Stack problem. The idea: scan the input once, pushing work onto a stack and popping when the top can be resolved, so the stack always reflects what's still open. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def removeDuplicates(self, s):
        st = []
        for ch in s:
            if st and st[-1] == ch:
                st.pop()
            else:
                st.append(ch)
        return ''.join(st)

Java

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

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);
            }
        }
        // Stack is in reverse order: top of stack = last char.
        // Walk it bottom-to-top to rebuild the answer.
        StringBuilder sb = new StringBuilder();
        Iterator<Character> it = stack.descendingIterator();
        while (it.hasNext()) sb.append(it.next());
        return sb.toString();
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.