Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Remove All Adjacent Duplicates In String

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"

.....

.....

.....

Like the course? Get enrolled and start learning!
C

camelBack

· 2 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
M

Meghana

· 2 years ago

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

Show 1 reply
L

lejafilip

· 2 years ago

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

Dante Tsang

Dante Tsang

· 4 months ago

this is not monotonic