개요

LeetCode #316, 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.

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

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.

collections.Counter()는 문자별 개수를 확인해줍니다. 입력으로 받은 문자열 s 중 현재 문자인 char가 stack에 쌓여 있는 문자(이전 문자보다 앞섬)이고, 뒤에 다시 붙일 문자가 있으면(counter > 0) 쌓인 것을 없앱니다.

import collections

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
            # Remove from stack if any characters remain to attach to the back
            while stack and char < stack[-1] and counter[stack[-1]] > 0:
                stack.pop()
            
            stack.append(char)
        
        return ''.join(stack)