Problem statement

https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/

Solution

This is one of that problems where you need to understand what is the topic: if you do it, then you will solve it, if you not, you can strugle quite a lot. Notice that here we consider groups of elements with the same value which are adjacent. If we delete them, another symbols will become adjacent. Stack is just ideal for this purposes.

So, we keep stack with pairs of elements: element itself and its frequency. Also I put in the beginning dummy variable, so I do not need to check if stack is empty. For each element we:

  1. Check if it is equal to the last element in stack, if it is, increase it frequency, if not - create new instance in stack with frequency 1.
  2. Check if we can delete groups of k equal elements: check if last frequency in stack is >=k and if it is, decrease it. Also if we get frequency equal to 0, delete element at all.

Complexity

It is just O(n) for time and space: we proceed every element at most twice: to put it to stack and to remove it from stack.

Code

class Solution:
    def removeDuplicates(self, s, k):
        stack = [["!", 1]]
        for elem in s:
            if elem == stack[-1][0]:
                stack[-1][1] += 1
            else:
                stack.append([elem, 1])
            
            while stack[-1][1] >= k:
                stack[-1][1] -= k
                if stack[-1][1] == 0: stack.pop()
             
        return "".join(i*j for i, j in stack[1:])