[LeetCode] Remove Duplicate Letters | stack | 파이썬 알고리즘 인터뷰, 정답, 소스코드

박상길, 『파이썬 알고리즘 인터뷰』를 정리한 내용입니다.

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

Remove Duplicate Letters - LeetCode

---

문제 요약

• 문자열이 주어질 때 문자열에서 중복된 문자를 제거하여 사전순으로 가장 빠른 문자열을 구하라. 

---

문제 조건

• 1 <= 문자열 길이 <= 10000

---

핵심 전략

• stack을 사용해 answer 저장
• stack에 push할 char이 stack.top보다 작고 counter[stack.top] > 0이면 pop하기

---

소스코드

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        counter, stack = collections.Counter(s), []

        for char in s:
            counter[char] -= 1
            if char in stack:
                continue
            
            while stack and char < stack[-1] and counter[stack[-1]] > 0:
                stack.pop()
            
            stack.append(char)
        
        return ''.join(stack)