LeetCode: Removing Adjacent Duplicates in a String

Today, we'll explore an elegant solution to remove adjacent duplicate characters from a string using a stack data structure. This problem is commonly encountered in coding interviews and has practical applications in text processing.

The Problem

Given a string, we need to remove all adjacent duplicate characters recursively. For example:

• Input: "abbaca" → Output: "ca"
• Input: "azxxzy" → Output: "ay"

Solution

function removeAdjacentDuplicates(str) {
  const stack = []

  for (let char of str) {
    const lastIndex = stack.length - 1

    if (stack[lastIndex] === char) {
      stack.pop()
    } else {
      stack.push(char)
    }
  }

  return stack.join('')
}

console.log(removeAdjacentDuplicates('abbaca')) // 'ca'
console.log(removeAdjacentDuplicates('azxxzy')) // 'ay'

Explanation

1. Initialize the Stack
We start by creating an empty array that will serve as our stack: const stack = []

2. Process Each Character
We iterate through each character in the input string using a for...of loop: for (let char of str)

3. Compare with Stack Top
For each character, we check if it matches the character at the top of the stack:stack[lastIndex] === char

4. Handle Duplicates
If we find a match (duplicate), we remove the top character using stack.pop(). Otherwise, we add the current character to the stack using stack.push(char).

5. Create Final String
Finally, we join all remaining characters in the stack to create our result: stack.join('')

Example Walkthrough

Let's see how the algorithm processes the input "abbaca":

Start with empty stack: []
Process 'a': stack = ['a']
Process 'b': stack = ['a', 'b']
Process 'b': stack = ['a'] :(remove 'b' as it's duplicate)
Process "a": stack = [] :(remove 'a' as it's duplicate)
Process 'c': stack = ['c']
Process 'a': stack = ['c', 'a']
Final result: "ca"