Question

LeetCode Link | 1047. Remove All Adjacent Duplicates In String | Easy

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.

We repeatedly make duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.

Constrains

  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters.

Examples

Example 1

Input: s = “abbaca”
Output: “ca”
Explanation:
For example, in “abbaca” we could remove “bb” since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is “aaca”, of which only “aa” is possible, so the final string is “ca”.

Example 2

Input: s = “azxxzy”
Output: “ay”

Solution Approach

Method: Stack

Constrains

  • None

This method does not have any limitations.

Concept Explanation

This problem requires deleting adjacent identical elements, which is similar to the parentheses matching in problem 20. Valid Parentheses that both are about matching—parentheses in the case of the problem 20. Valid Parentheses and adjacent elements in this problem, ultimately leading to an elimination operation.

This is also a classic problem solved using stacks.

So, what elements should be placed in the stack?

When deleting adjacent duplicates, we need to know if the current element we are traversing has the same value as the element immediately preceding it. How do we keep track of previously traversed elements?

Thus, we use a stack to store elements. The stack’s purpose is to store traversed elements, so when traversing the current element, we check the stack to see if we have previously encountered an adjacent element with the same value.

Then, we perform the corresponding elimination operation, as illustrated in the figure below:

Remove Example

Code

  • Time complexity: O(n)
  • Space complexity: O(n)

TypeScript

1
2
3
4
5
6
7
8
9
10
11
function removeDuplicates(s: string): string {
    let stack: string[] = [];
    for (let i of s) {
        let top: string = stack[stack.length - 1];
        // Remove if adjacent is duplicate
        if (top === i) stack.pop();
        // Add into stack if not duplicate
        else stack.push(i);
    }
    return stack.join('');
};

Conclusion

Easy startup question, remember use stack for problem that relates on symmetry matching problems. For more detail, check solution for problem 20. ValidParentheses.