Remove All Adjacent Duplicates In String

easy stack string

Problem

You are given a string s of lowercase English letters. A duplicate removal deletes two adjacent equal characters. Repeatedly perform duplicate removals until no more can be made, and return the final string. The answer is guaranteed to be unique.

Inputs = "abbaca"

Output"ca"

Remove "bb" to get "aaca", then remove "aa" to get "ca". No adjacent duplicates remain.

s (lowercase letters)

def remove_duplicates(s):
    stack = []
    for ch in s:
        if stack and stack[-1] == ch:
            stack.pop()
        else:
            stack.append(ch)
    return "".join(stack)

function removeDuplicates(s) {
  const stack = [];
  for (const ch of s) {
    if (stack.length && stack[stack.length - 1] === ch) {
      stack.pop();
    } else {
      stack.push(ch);
    }
  }
  return stack.join("");
}

class Solution {
    public String removeDuplicates(String s) {
        StringBuilder stack = new StringBuilder();
        for (char ch : s.toCharArray()) {
            int n = stack.length();
            if (n > 0 && stack.charAt(n - 1) == ch) {
                stack.deleteCharAt(n - 1);
            } else {
                stack.append(ch);
            }
        }
        return stack.toString();
    }
}

string removeDuplicates(string s) {
    string stack;
    for (char ch : s) {
        if (!stack.empty() && stack.back() == ch) {
            stack.pop_back();
        } else {
            stack.push_back(ch);
        }
    }
    return stack;
}

Explanation

This problem looks like it needs many passes — remove a pair, the neighbours might now touch, remove again, and so on. The clever shortcut is a stack that lets us do it all in a single left-to-right scan.

The rule is tiny: as we read each character ch, we compare it to whatever is currently on top of the stack. If they are equal, those two are an adjacent duplicate pair, so we pop the top off (removing both). If they are different, we push ch on.

Why does one pass suffice? When we pop a pair, the new top is the character that came before the deleted pair. That is exactly the character now sitting next to our next letter, so any new adjacency is handled automatically on the very next step.

Example: s = "abbaca". Push a, push b. Next b matches the top, so pop → stack is [a]. Next a matches the top, pop → stack is empty. Push c, push a. Joining the stack gives "ca".

At the end, the characters left on the stack, read bottom to top, are the final answer.

Time: O(n) Space: O(n)