리트코드 316번 Remove Duplicate Letters (Python)

Problem

https://leetcode.com/problems/remove-duplicate-letters/description/

Solution

from collections import Counter

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        counter = Counter(s)
        stack = []
        for c in s:
            counter[c] -= 1
            if c in stack:
                continue

            while stack and stack[-1] > c and counter[stack[-1]] > 0:
                stack.pop()

            stack.append(c)
        return ''.join(stack)

주어진 문자열의 글자를 하나씩 stack에 넣는다. 이때, 주어진 글자가 stack의 마지막 글자보다 앞선 글자라면 stack의 마지막 글자를 pop하는데, 만약 pop할 글자가 뒤에 더 나오지 않는다면 제거하지 않고 새로운 글자를 stack에 넣는다.

Reference

파이썬 알고리즘 인터뷰 21번