Grokking Meta Coding Interview
Vote

0% completed

​

Remove All Adjacent Duplicates In String (easy)

Problem Statement

Try it yourself

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.

A note on the pattern. This question uses a stack, but not a monotonic one: nothing here keeps the stack in increasing or decreasing order. It sits in this chapter because it builds the habit every monotonic stack question needs, which is deciding what to do with a new item by looking at the top of the stack and popping when a condition holds. The ordering invariant arrives in the questions after it.

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.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .
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

Try it yourself