Skip to main content

1209. Remove All Adjacent Duplicates in String II

Python​

Recusive (Timelimit Exceed)​

from typing import List


class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        remove_periods = self.find_remove_periods(s, k)
        if not remove_periods:
            return s

        s_array = []
        cur = 0
        for start, end in remove_periods:
            s_array.append(s[cur:start])
            cur = end + 1
        s_array.append(s[cur:])

        return self.removeDuplicates(''.join(s_array), k)

    def find_remove_periods(self, s: str, k: int) -> List:
        pre = ''
        count = k
        remove_periods = []
        for i, char in enumerate(s):
            if char == pre:
                count -= 1
                if count == 1:
                    remove_periods.append((i-k+1, i))
            else:
                count = k
                pre = char
        return remove_periods

Count with Stack​

  • Time: O(N)
  • Space: O(N) # The addition space for stack
class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stack = []

        for i, char in enumerate(s):
            if not stack:
                stack.append([char, 1])
                continue

            if stack[-1][0] == char:
                stack[-1][1] += 1
            else:
                stack.append([char, 1])

            if stack[-1][1] == k:
                stack.pop()

        s_array = []
        for char, count in stack:
            s_array.append(char*count)

        return ''.join(s_array)