문제

leetcode 316. Remove Duplicate Letter
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.

중복된 문자를 제외하고 사전식 순서(Lexicogaphical Order)로 나열하는 문제입니다.

#예시
Input: s = "cbacdcbc"
Output: "acdb"

풀이

"""
Runtime: 24 ms, faster than 98.89% of Python3 online submissions for Remove Duplicate Letters.
Memory Usage: 14.2 MB, less than 33.32% of Python3 online submissions for Remove Duplicate Letters.
"""
import collections

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        counter, seen, stack = collections.Counter(s), set(), []
        
        for char in s :
            counter[char] -= 1
            if char in seen :
                continue
            while stack and char < stack[-1] and counter[stack[-1]] > 0:
                seen.remove(stack.pop())
            stack.append(char)
            seen.add(char)
        
        return ''.join(stack)
        

s = "cbacdcbc" 라면,
counter는 Counter({'c': 4, 'b': 2, 'a': 1, 'd': 1})이고,
seen은 비어있는 set(), stack은 비어있는 리스트 []입니다.

반복문을 통해 s의 맨 처음 글자부터 보게되고, 해당 문자의 counter[char]에 해당하는 빈도수를 1 감소시킵니다.

 while stack and char < stack[-1] and counter[stack[-1]] > 0:
        seen.remove(stack.pop())

현재 문자 char가 stack에 쌓여있는 문자(이전문자 stack[-1])보다 앞선 문자이고, stack에 쌓여있는 문자가 뒤에 남아있다면(counter[stack[-1]]>0)
쌓아둔 걸 없앱니다.

if char in seen :
	continue

위와같이 조건문으로 char이 앞에서 이미 stack에 쌓여있는지 확인하여, 이미 처리된 문자를 스킵합니다.

최종적으로 사전식 순서에 맞게 스택한 리스트 stack을 문자열로 반환합니다.