Code Logo

Remove All Adjacent Duplicates in String

Published at23 Jul 2026
Created by
Easy 1 views
Like0

You are given a string consisting of lowercase letters. Repeatedly remove two adjacent duplicate characters until no more adjacent duplicates exist. Return the final string.

A stack makes this trivial: iterate through each character. If the stack is not empty and the top of the stack equals the current character, pop the stack (removing the pair). Otherwise, push the character onto the stack. At the end, the stack contains the remaining characters in order.

For example, "abbaca"→ push a, push b, b matches top b → pop b, stack=[a], push a, a matches top a → pop a, stack=[], push c, push a → result = "ca".The stack elegantly solves this by comparing the current character with the top of the stack. If they match, both disappear (pop). If they don't match, the current character stays (push). This naturally handles cascading removals, like removing bb from abba, which then makes aa adjacent.This problem teaches the concept of a stack as a simplifier or reducer. The repeated removal of adjacent pairs is analogous to化学反应 or collision problems where pairs annihilate each other.

This problem is commonly asked in phone screens and entry-level interviews. It tests whether you recognize that a stack can simplify repeated removals that would otherwise require complex index manipulation with a regular array or string builder. The single-pass stack approach is both cleaner and faster than repeatedly scanning the string.

Example Input & Output

Example 1
Input
abbaca
Output
ca
Explanation

bb is a pair → removed. Then aa becomes adjacent and is removed.

Example 2
Input
abba
Output
Explanation

bb is removed. Then aa becomes adjacent and is removed. Empty result.

Example 3
Input
a
Output
a
Explanation

Single character, no duplicates.

Example 4
Input
azxxzy
Output
ay
Explanation

xx is removed. Then zz becomes adjacent and is removed.

Algorithm Flow

Recommendation Algorithm Flow for Remove All Adjacent Duplicates in String

Solution Approach

Remove all adjacent duplicates in a string repeatedly until no more adjacent duplicates exist. Use a stack: push each character onto the stack. If the next character matches the top of the stack, pop the stack instead of pushing.

function removeDuplicates(s) {
  var stack = [];
  for (var i = 0; i < s.length; i++) {
    if (stack.length > 0 && stack[stack.length - 1] === s[i]) {
      stack.pop();
    } else {
      stack.push(s[i]);
    }
  }
  return stack.join('');
}

Iterate through each character. If the stack is non-empty and the top of the stack matches the current character, pop (remove the pair). Otherwise, push the current character. The remaining stack contains the string with all adjacent duplicates removed.

Time complexity is O(n), space complexity is O(n).

Best Answers

java
import java.util.*;
class Solution {
    public String solution(String s) {
        Stack<Character> stack = new Stack<>();
        for (char ch : s.toCharArray()) {
            if (!stack.isEmpty() && stack.peek() == ch) stack.pop();
            else stack.push(ch);
        }
        StringBuilder sb = new StringBuilder();
        for (char ch : stack) sb.append(ch);
        return sb.toString();
    }
}