1209. Remove All Adjacent Duplicates in String II (String, Stack)

링크 - https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

우리는 stack을 사용해 이 문제를 풀 수 있다. 먼저 stack의 peak를 항상 체크하면서 현재 글자와 같은 글자가 stack의 peak에 있고 그 값이 k-1이면, 우리는 중복을 제거할 수 있으므로 그냥 Pop한다. 그게 아니면 새로 [c,1]을 넣거나 stack[-1][1] += 1을 해준다. 중요한건 tuple로 하면 stack[-1][1] += 1이 안되고 pop & append를 해줘야 하므로 반드시 (c,1)이 아닌 [c,1]인 list로 문제를 풀자.

Code

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stack = []

        for c in s:
            if not stack or stack[-1][0] != c:
                stack.append([c, 1])
            else:
                if stack[-1][1] == k-1:
                    stack.pop()
                else:
                    stack[-1][1] += 1

        return ''.join(c*k for c, k in stack)

Complexity

Time Complexity: O(N)

Space Complexity: O(N)