[Leetcode] - 316

• Counter를 사용해 문자별 개수 계산
• seen list를 별도로 만든 이유는 stack ADT 에 따르면 stack은 검색 기능이 없기 때문
• 지금까지 등장한 답변에 사용될 문자들은 seen (set)으로 검사
• i번째 등장한 문자가 이전에 stack 에 쌓여있는 (정답으로 쓰일) 문자보다 사전순으로 빨리등장하고, 그 문자가 뒤에서 다시 등장한다면 해당 문자를 stack에서 제거
• stack 에 있는 모든 문자와 크기 비교하지 않음 (모든 문자마다 반복하면 되기 때문에) 마지막 문자만 크기 비교
• 시간복잡도 O(N)
• 공간복잡도 O(N)

from collections import Counter

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

• 주어진 str의 모든 문자가 등장하고, 문자의 순서를 바꾸는것 없이 가장 빠른 사전순의 문자열의 첫번째 문자를 찾는다

• 재귀 형태로 반복 수행한다

• 해당 문자를 가장 앞문자로 했을 때 하위 문자열에서 전체 문자열의 문자들이 빠짐없이 모두 등장한다면 해당 문자를 선택

• the smallest character such that its suffix contains at least one copy of every character in the string.

  suffix = s[s.index(c):]
  set(s) == set(suffix)

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:        
        for c in sorted(set(s)):
            suffix = s[s.index(c):]
            if set(s) == set(suffix):
                return c + self.removeDuplicateLetters(suffix.replace(c,''))
        return ''