[코테] 리트코드 스택,큐 316. Remove Duplicate Letters

316. Remove Duplicate Letters

문제 링크

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

문제 설명

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.

제한 사항

• 1 <= s.length <= 10^4
• s consists of lowercase English letters.

입출력 예 #1

1. Input: s = “bcabc”
2. Output: “abc”

입출력 예 #2

1. Input: s = “cbacdcbc”
2. Output: “acdb”

문제 풀이

1. 재귀를 활용한 문제 풀이
2. 뒤에 붙일 문자가 남아있다면 스택에서 제거하는 형식으로 문제 풀이

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 ''

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)