Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Remove All Adjacent Duplicates in String II

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

This solution doesn't need to reconstruct the counts.

        stack = []
        for c in s:
            if stack and stack[-1][-1] == c:
                stack[-1] += c
            else:
                stack.append(c)
            
            if stack and len(stack[-1]) == k:
                stack.pop()

        return "".join(stack)
A

Anonymous

· 2 years ago

Push and pop for vector are expensive because we force processor for realocate memory every push and pop.

In list we have back() which is constant. W doesn't want iterate over list.

A

Anonymous

· 2 years ago

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stack = []
        for index, char in enumerate(s):
            # if we have reached k count for the same character
            if len(stack) > 0 and char == stack[-1][0] and stack[-1][1] == k - 1:
                # keep popping
                count = 0
                while count < k - 1:
                    count += 1
                    stack.pop()
            else: # push the character
                # if pervious character is the same as the character from the loop
                if len(stack) > 0 and char == stack[-1][0]:
                    stack.append((char, stack[-1][1] + 1))
                else:
                    stack.append((char, 1))
        return "".join([x for x,y in stack]);
A

Anonymous

· 2 years ago

I think there is a mismatch between the constraints and the Submit test cases. The constraints mention

2 <= k <= 104

However, one of the Submit cases is

"aabbbbccdd" 1

Show 1 reply

Reading Progress

0%

Vote for new content