[Leetcode] 316.Remove Duplicate Letters

중복 문자 제거

316. Remove Duplicate Letters

 

https://leetcode.com/problems/remove-duplicate-letters/

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.

 

Example 1:

Input: s = "bcabc" Output: "abc"

Example 2:

Input: s = "cbacdcbc" Output: "acdb"

 

Constraints:

• 1 <= s.length <= 104
• s consists of lowercase English letters.

 

Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

-----------------------------------------------------------------------------------------------------------------------------------

풀이 1. 재귀를 이용한 분리

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

 

풀이 2. 스택을 이용한 문자 제거

 

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)