Leetcode 1081. Smallest Subsequence of Distinct Characters

문제

Given a string s, 
return the lexicographically smallest subsequence of s 
that contains all the distinct characters of s exactly once.

• 주어진 문자열 s에 대해 사전순으로 가장 작은 subsequence를 리턴하시오
• 다만 subsequence는 s에 등장하는 모든 문자를 한종류씩 다 가지고 있다.

예시

• cbabc
• abc가 정답

제한

• 1 <= s.length <= 1000
• s는 영 소문자로만 이루어져 있다.

풀이

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        last_place = defaultdict(int)

        for index, ch in enumerate(s):
            last_place[ch] = index

        placement = set()
        stack = []

        for index, ch in enumerate(s):
            if ch in placement:
                continue

            while stack and ord(stack[-1]) > ord(ch):
                if last_place[stack[-1]] > index:
                    c = stack.pop()
                    placement.remove(c)
                else:
                    break

            stack.append(ch)
            placement.add(ch)


        return "".join(stack)

• increasing monotonic stack 을 쓰되
• 한번만 등장하도록 하고
• 더이상 등장하지 않을 문자는 빼지 않는다.