Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Solution: Remove All Adjacent Duplicates In String

Problem Statement

Give a string s, convert it into a valid string. A string is considered valid if it does not have any two adjacent duplicate characters.

To make a string valid, we will perform a duplicate removal process. 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

Example 1

  • Input: "abbaca"
  • Expected Output: "ca"

.....

.....

.....

Like the course? Get enrolled and start learning!
R

reagankm

· 2 years ago

The solution code doesn't match the algorithm and diagram. The solution code is perhaps a better implementation, but you ought to change something so these match.

The algorithm and diagram say that at the end you pop the elements from the stack (which gives you the string in the wrong order), and then you reverse the string.

The code doesn't pop elements from the stack, instead it accesses elements in a for loop so they're already in the correct order.

tai

tai

· 2 years ago

Maybe this isn't the "right" approach but since this is a stack problem, iterating over the string in sequential order would end up with a reverse answer, so instead of reversing the stack (which I'm pretty sure goes against the constraints of a stack) I figured you could just iterate over the string from the opposite end. I know JS doesn't include a "peek" method so I decided to just use the stack length to access the ending element (for some reason my browser/code editor won't accept stack.at(-1) but I think this is a bit more reasonable than the given answer in the solution section:

class Solution {

removeDuplicates(s) {
    // ToDo: Write Your Code Here.
        const stack = []
        for (let i = s.length - 1; i > -1; i--) {
            if (stack.length && stack.at
Tó Rugain

Tó Rugain

· 9 months ago

Since you are using a stack, and the session clearly talk about a stack, at the end of this solution you are doing a JOIN with a stack. A stack is a structure that only can be iterated with pop() method (you only know the last element), and join takes the first position of a interable, till the last position, breaking the concept of a stack. This solution follows the real concept of a stack

def removeDuplicates(self, s):
        # ToDo: Write Your Code Here.
        stack = []
        result = []
        for pos in range(len(s)):
            if stack and s[pos] == stack[-1]:
                stack.pop()
                continue
            stack.append(s[pos])
        
        while stack:
            result.append(stack.pop())
        
        result.reverse()
        return "".
George Ceja

George Ceja

· 4 months ago

Here's a more readable copy in Python

class Solution:
    def removeDuplicates(self, s):
        # ToDo: Write Your Code Here.
        stack = []

        for _, char in enumerate(s):
            if stack == []:
                stack.append(char)
                continue

            if stack[-1] != char:
                stack.append(char)
            else:
                stack.pop()

        return ''.join(stack)