Solution: Remove All Adjacent Duplicates In String

Statement

You are given a string consisting of lowercase English letters. Repeatedly remove adjacent duplicate letters, one pair at a time. Both members of a pair of adjacent duplicate letters need to be removed.

Constraints:

• $1 \leq$ string.length $\leq 10^3$
• string consists of lowercase English alphabets.

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach is to generate a set of all possible adjacent duplicates in a string of small English alphabets, that is, {"aa", "bb", "cc", "dd", ...}. Traverse over the string to see if such duplicates are present. We’ll use nested loops to check this condition. If duplicate characters are found, we’ll remove the adjacent duplicates from the input string. For example, in the "abaac" string, we’ll remove "aa" from the string, which results in "abc".

Since we’re using nested loops, the time complexity of this approach is $O(n^2)$, which is not optimal. Let’s see if we can use the stacks pattern to reduce the time complexity of our solution.

Optimized approach using stacks

We can remove adjacent duplicates in pairs, which is similar to matching opening and closing parentheses. In such problems, we typically use stacks to store intermediate results to deal with nested pairs of parentheses. We’ll use the same concept here.

We’ll initialize a stack first. Then, we’ll iterate the complete string from left to right, and for every character, we’ll check the following:

• If the stack is empty, we’ll push the character onto the stack.
• If the stack is not empty, we’ll perform the following tasks:
  • If the string’s character is different from the stack’s top character, we’ll push the string’s character onto the stack because we did not find the adjacent duplicate.
  • If the string’s character is the same as the stack’s top character, it means that we found the adjacent duplicate characters. We’ll pop that character from the stack and move to the next character in the string.
• After the entire string has been traversed, the remaining characters in the stack will be our result. We’ll form a string from those characters and return it.

The slides below illustrate how we’d like the algorithm to run: