Leetcode - Remove All Adjacent Duplicates In String Solution

Removing adjacent duplicates from a string sounds simple at first, but it gets tricky when removals create new adjacent pairs. 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 made it elegant and efficient.

The key insight is that a stack naturally handles the "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;
}

This works, but it's O(n²) in the worst case because we might need multiple passes. Each pass takes O(n) time, and in the worst case (like "aaaa"), we might need n/2 passes. I knew there had to be a better way.

The Stack Insight

The breakthrough came when I realized a stack is perfect for this problem. The stack's LIFO (Last In, First Out) property naturally 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

This way, we only need one pass through the string!

The Solution

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

How It Works

Let me trace through "abbaca" step by step:

• 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 key insight is that when we pop a duplicate, we're effectively "undoing" the previous addition. The new top of the stack might now match the next character, creating a cascading removal effect without needing multiple passes.

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, this is still better than 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're comparing characters, not indices
3. Joining the result: Don't forget to join the stack array at the end
4. Edge cases: Empty strings should return empty strings

Key Takeaways

• Stacks are perfect for matching/removing pairs
• The LIFO property naturally handles "undo" operations
• Sometimes the right data structure makes the algorithm trivial
• One pass is often possible with the right structure
• This pattern appears in many string manipulation problems (matching brackets, removing duplicates, etc.)

The stack solution is so much cleaner than my first attempt! This problem really showed me how choosing the right data structure can simplify an algorithm dramatically. Once you see the pattern, you'll recognize opportunities to use stacks in many similar problems involving matching pairs or cascading removals.