Remove All Adjacent Duplicates In String

Return string but remove all the duplicates (Remove both the duplicate do not make them unique)

Remove All Adjacent Duplicates In String

Problem

You are given a string s made of lowercase English letters.

A duplicate removal means choosing two adjacent and equal letters and removing them.

We keep doing duplicate removals until we cannot do any more. Return the final string. The answer is always unique.

Examples

Example 1

Input: s = "abbaca"
Output: "ca"

• We remove bb, so the string becomes "aaca".
• Now we remove aa, so the string becomes "ca".
• No more adjacent equal letters are left, so the answer is "ca".

Example 2

Input: s = "azxxzy"
Output: "ay"

• We remove xx, so the string becomes "azzy".
• Now we remove zz, so the string becomes "ay".

Constraints

• 1 <= s.length <= 10^5
• s has only lowercase English letters.

Main Idea

When we remove a pair, the letters on its left and right can become new neighbors. They may form a new pair. So we need a way to check the most recent letter we kept. This is a perfect job for a stack.

We read the string from left to right. For each letter, we compare it with the top of the stack.

• Letter is equal to the top: This is a duplicate pair. We pop the top. Both letters are removed.
• Letter is not equal to the top (or the stack is empty): We push the letter.

At the end, the stack holds the final string.

Note: The top of the stack is always the last letter that is still in the string. So comparing with the top is the same as checking the adjacent letter.

Stack Class Used in the Solution

The solution uses a Stack class with push, pop, peek and isEmpty. Here is a small version of it.

class Stack {
    constructor() {
        this.items = [];
    }

    push(element) {
        this.items.push(element);
    }

    pop() {
        if (this.isEmpty()) return "Stack Underflow";
        return this.items.pop();
    }

    // returns null when the stack is empty
    peek() {
        return this.isEmpty() ? null : this.items[this.items.length - 1];
    }

    isEmpty() {
        return this.items.length === 0;
    }
}

Solution: Stack

var removeDuplicates = function (s) {
    let stack = new Stack();

    let arr = s.split('');
    let result = [];

    for (let st of arr) {
        if (stack.peek() == st) {
            // same as the top, so remove the pair
            stack.pop();
        } else {
            // different from the top, so keep it
            stack.push(st);
        }
    }

    // take all letters out of the stack
    while (!stack.isEmpty()) {
        result.push(stack.peek());
        stack.pop();
    }

    // letters came out from last to first, so reverse them
    return result.reverse().join('');
};

How the Code Works

Step 1: Create the stack and the array

• stack keeps the letters that are still in the string.
• arr is the string split into single letters.
• result is an empty array. We will use it at the end.

Step 2: Read each letter

• stack.peek() gives the top letter, or null if the stack is empty.
• If the top is equal to the current letter, we call stack.pop(). The pair is gone.
• Otherwise, we call stack.push(st). The letter stays for now.
• When the stack is empty, peek() gives null. A letter is never equal to null, so the letter is pushed. This is why we never pop from an empty stack.

Step 3: Build the answer

• We take letters out of the stack one by one with peek() and pop().
• The top comes out first, so the letters come out in reverse order.
• We call reverse() to fix the order, and join('') to make a string.

Dry Run

Let us take s = "abbaca".

The stack is [c, a]. We take the letters out as a, c, then reverse them to get "ca".

Notice the fourth row. After bb was removed, the first a and the second a became neighbors. The stack found this pair easily.

Complexity

• Time Complexity: O(n)
  • n is the length of the string.
  • Each letter is pushed at most once and popped at most once.
  • Building the result also takes O(n), including the reverse() and join().
• Space Complexity: O(n)
  • In the worst case, no pair is removed, so the stack holds all n letters.
  • The arr and result arrays also use O(n) space.

Shorter Version (Optional)

We can use a plain array as the stack. It also removes the extra result array, because the array already holds the letters in the correct order.

var removeDuplicates = function (s) {
    let stack = [];

    for (let ch of s) {
        if (stack.length > 0 && stack[stack.length - 1] === ch) {
            // same as the top, so remove the pair
            stack.pop();
        } else {
            // different from the top, so keep it
            stack.push(ch);
        }
    }

    return stack.join('');
};

Complexity

• Time Complexity: O(n), because each letter is pushed and popped at most once.
• Space Complexity: O(n), because the stack can hold all letters.

Comparison

Summary

• When a pair is removed, the letters around it can become a new pair. So we need the last kept letter each time.
• A stack gives us that letter at the top in O(1) time.
• If the current letter equals the top, pop. Otherwise, push.
• The stack at the end is the final string. In the class version, letters come out in reverse, so we reverse them.
• The solution runs in O(n) time and uses O(n) space.