Problem statement

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

Solution

Similar to leetcode 1209. Remove All Adjacent Duplicates in String II, 1047. Remove All Adjacent Duplicates In String. What we need to do is to use stack:

  1. If we have last element of stack equal to new element, remove it from stack.
  2. If we have new element not equal to previous, add it to stack.
  3. Also update previous element.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s):
        prev = "!"
        stack = [prev]
        for char in s:
            if stack[-1] == char:
                stack.pop()
            elif char != prev:
                stack.append(char)
            prev = char
        return "".join(stack[1:])