BinarySearch 0627 Repeated Deletion Sequel

Problem statement

https://binarysearch.com/problems/Repeated-Deletion-Sequel/

Solution

Equal to Leetcode 1209. Remove All Adjacent Duplicates in String II.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s, k):
        stack = [["!", 0]]
        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:])