1047. Remove All Adjacent Duplicates In String

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

난이도 - Easy

Intuition

stack을 사용하면 아주쉽게 풀 수 있다.

Code

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []
        for c in s:
            if stack and stack[-1] == c:
                stack.pop()
            else:
                stack.append(c)
        return "".join(stack)

Complexity

Time Complexity: O(N)

Space Complexity: O(N-D) 여기서 D는 duplicates들의 총 길이이다.