❗️[LEET CODE] 316. Remove Duplicate Letters

# Problem

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. Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/   Constraints: 1 <= s.length <= 104 s consists of lowercase English letters.

 

# Solution 1 - 재귀를 이용한 분리

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        # 집합으로 정렬
        for char in sorted(set(s)):
            suffix = s[s.index(char):]
            # 전체 집합과 접미사 집합이 일치할때 분리 진행
            if set(s) == set(suffix):
                return char + self.removeDuplicateLetters(suffix.replace(char, ''))
        return ''

 

# Solution 2 - 스택을 이용한 문자 제거

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)

현재 문자 char 가 스택에 쌓여 있는 문자보다 앞선 문자이고 스택에 쌓여있는 문자가 뒤에 더 남아 있다면(카운터 0 이상이면) 쌓아둔 걸 없앤다