Leetcode - Remove All Adjacent Duplicates In String Solution

A removal of adjacent duplicate characters can create another pair that must also be removed. For example, "abbaca" becomes "aaca" after removing "bb", then "ca" after removing "aa". My first solution kept iterating until no more duplicates were found, but a stack handles the cascading removals in one pass.

A stack supports this "remove and check again" behavior. When we see a character that matches the top of the stack, we pop it (removing the duplicate). Otherwise, we push it. This automatically handles cascading removals in a single pass.

Understanding the Problem

Given a string, repeatedly remove pairs of adjacent duplicate characters until no more duplicates exist. For example:

• "abbaca" → remove "bb" → "aaca" → remove "aa" → "ca"

The challenge is doing this efficiently. A naive approach might require multiple passes, but we can do it in a single pass with the right data structure.

My First Approach

My initial solution kept scanning and removing duplicates until no more were found.

function removeDuplicatesNaive(str) {
  let result = str;
  let found = true;

  while (found) {
    found = false;
    let temp = "";

    for (let i = 0; i < result.length; i++) {
      if (i < result.length - 1 && result[i] === result[i + 1]) {
        i++; // Skip both characters
        found = true;
      } else {
        temp += result[i];
      }
    }

    result = temp;
  }

  return result;
}

The repeated scans take O(n²) time in the worst case. A pass scans the remaining characters, and some inputs need n/2 removal passes. The input "aaaa" is not such a case: the first pass removes both pairs.

The Stack Insight

A stack fits this problem because its LIFO (Last In, First Out) property handles the "remove and check again" behavior:

• When we see a character, if it matches the top of the stack, we pop (removing the duplicate)
• Otherwise, we push the character
• When we pop a duplicate, the new top might match the next character, automatically handling cascading removals

The algorithm reads each input character once.

Stack implementation

function removeDuplicates(str) {
  const stack = [];

  for (let char of str) {
    // If stack is not empty and top matches current char, pop (remove duplicate)
    if (stack.length > 0 && stack[stack.length - 1] === char) {
      stack.pop();
    } else {
      // Otherwise, push the character
      stack.push(char);
    }
  }

  // Join remaining characters
  return stack.join("");
}

Stack trace

For "abbaca", the stack changes as follows:

• Process 'a': stack is empty, push 'a' → stack = ['a']
• Process 'b': top is 'a' (different), push 'b' → stack = ['a', 'b']
• Process 'b': top is 'b' (match!), pop → stack = ['a']
• Process 'a': top is 'a' (match!), pop → stack = []
• Process 'c': stack is empty, push 'c' → stack = ['c']
• Process 'a': top is 'c' (different), push 'a' → stack = ['c', 'a']

Result: "ca"

The duplicate removal reverses the previous addition to the stack. The new top can match the next input character. This comparison handles further removals during the same scan.

Why This Works

The stack naturally handles the cascading removal behavior:

• LIFO property: The last character added is the first one we check against
• Automatic cascading: When we pop a duplicate, the new top might match the next character
• Single pass: We process each character exactly once
• Efficient: O(n) time and O(n) space in the worst case

Complexity Analysis

Time Complexity: O(n)

• Single pass through the string
• Each character is processed exactly once
• Stack operations (push/pop) are O(1)

Space Complexity: O(n)

• In the worst case, we might store all characters in the stack (e.g., "abc" with no duplicates)
• However, it avoids creating multiple intermediate strings

Common Pitfalls

When implementing this, watch out for:

1. Empty stack check: Always check if the stack is empty before accessing the top
2. Index vs value: Make sure you are comparing characters, not indices
3. Joining the result: Do not forget to join the stack array at the end
4. Edge cases: Empty strings should return empty strings

What the stack gives us

• Stacks handle matching and removal pairs through LIFO semantics
• A single pass can handle cascading removals
• The same pattern applies to matching brackets and related string problems

The stack solution is cleaner than my first attempt. Choosing the right data structure simplifies the algorithm and helps with other matching or cascading removal problems.