Grokking Meta Coding Interview
Vote

0% completed

​

Solution: Remove All Adjacent Duplicates In String

Problem Statement

Why this is a Monotonic Stack problem

Solution

Code

Time and Space Complexity

Problem Statement

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.

Examples

    • Input: s = "abccba"
    • Output: ""
    • Explanation: First, we remove "cc" to get "abba". Then, we remove "bb" to get "aa". Finally, we remove "aa" to get an empty string.
    • Input: s = "foobar"
    • Output: "fbar"
    • Explanation: We remove "oo" to get "fbar".
    • Input: s = "fooobar"
    • Output: "fobar"
    • Explanation: We remove the pair "oo" to get "fobar".
    • Input: s = "abcd"
    • Output: "abcd"
    • Explanation: No adjacent duplicates so no changes.

Constraints:

  • 1 <= s.length <= 10<sup>5</sup>
  • s consists of lowercase English letters.

Why this is a Monotonic Stack problem

What the question saysThe signal it matches
"choosing two adjacent and equal letters and removing them"each character is resolved against its most recent neighbour
"We repeatedly make duplicate removals on s until we no longer can"a removal can expose a new pair, so the process cascades
rescanning the whole string after every removalyour first idea is to scan the input repeatedly

Each new character cancelling the one on top is the cancel out neighbours variant.

The closest alternative. Repeated string scanning is the alternative, and it is quadratic. One removal in the middle can force a fresh pass over the string.

There is no ordering rule here, so a plain stack is enough. The introduction says the same: only the most recent item matters. The problem appears in this chapter because the cancelling shape is the one the harder problems use.

Solution

This problem can be solved efficiently using a stack, which can mimic the process of eliminating adjacent duplicates.

Algorithm Walkthrough

  1. Initialize an empty stack.
  2. Loop through the characters in the given string s.
  3. For each character:
    • If the stack is not empty and the current character is the same as the top character on the stack, pop the character from the stack.
    • Otherwise, push the current character onto the stack.
  4. Finally, build the result string from the characters remaining on the stack.
mediaLink

s = "fooobar". Scan left to right with a stack: a character equal to the top cancels it (pop); otherwise push.

1 of 9

Code

Here is the code for this algorithm:

Python3
Python3
. . . .

Time and Space Complexity

The time complexity of this algorithm is O(N), where N is the length of s, because we perform one operation per character in s. The space complexity is also O(N), as in the worst case, every character in s is pushed onto the stack.

Dante Tsang

Dante Tsang

· 5 months ago

this is not monotonic

Show 1 reply
L

lejafilip

· 2 years ago

I mean at the end we use "reverse". Shouldn't we create other solution without that?

M

Meghana

· 2 years ago

since all of o's are duplicates, shouldnt the answer be fbar? why is it fobar?

Show 1 reply
C

camelBack

· 3 years ago

The question is deceiving a bit - asking for a recursive solution, while the sample answer is not a recursive answer.

Also, what about more than 2 adjacent characters? 'abcccba'?

Show 3 replies

Reading Progress

0%

Vote for new content

On This Page

Problem Statement

Why this is a Monotonic Stack problem

Solution

Code

Time and Space Complexity