LeetCode - 316. Remove Duplicate Letters (Python)

Medium, 스택

RunTime : 35 ms / Memory : 16.63 MB

문제

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is
the smallest in lexicographical order among all possible results.

풀이

• 핵심이 되는건 현재 탐색중인 w보다 사전순으로 뒤인 글자가
  w보다 앞에 위치할 때, 이를 어떻게 해결할 것인가 이다.
• collections의 Counter 모듈을 통해 s내의 각 알파벳의 개수를 센 후,
  탐색할 때마다 현재 w를 기준으로 stack을 조정해준다.
• 또한 하나만 들어가야 하므로 set을 통해 한개씩만 들어갈 수 있도록 유지한다.

from collections import Counter
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        stack = []
        counter = Counter(s)
        isIn = set()

        for w in s:
            counter[w] -= 1

            if w in isIn:
                continue
            
            while stack and stack[-1] > w and counter[stack[-1]] > 0:
                # 뒤에 현재 stack[-1]의 문자가 남아있음
                # 현재 w가 stack[-1]보다 사전순으로 앞임
                isIn.remove(stack.pop())
            
            stack.append(w)
            isIn.add(w)

        return ''.join(stack)