Code Logo

Remove All Adjacent Duplicates in String

Published at23 Jul 2026
Created by
Easy 0 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".

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
Recommendation Algorithm Flow for Remove All Adjacent Duplicates in String

Solution Approach

Create a stack (array). Iterate through each character. If the stack is not empty and the top equals the current character, pop. Otherwise, push. Join the stack at the end.

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

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();
    }
}