1 min to read

[LeetCode] #1081, #316

Smallest Subsequence of Distinct Characters

Featured image

Blind에 1081번 문제에 대한 글이 hot해서 한번 풀어보았다. blind capture

문제

Return the lexicographically smallest subsequence of s that contains all the distinct characters of s exactly once.

Example 1:
Input: s = “bcabc”
Output: “abc”

Example 2:
Input: s = “cbacdcbc”
Output: “acdb”

풀이

하나씩 loop를 돌면서 현재 문자보다 앞에 나올 필요가 없는 문자들을 pop 해주며 stack에 쌓으면 된다.

class Solution(object):
    def smallestSubsequence(self, s):
        counter = collections.Counter(s)
        stack = []
        
        for c in s:
            counter[c] -= 1
            if c in stack:
                continue
            while stack and c < stack[-1] and counter[stack[-1]] > 0:
                stack.pop()
            stack.append(c)
        
        return ''.join(stack)

풀고나서 보니 316번과 동일한 문제였는데, 반년 전에 이미 푼 문제였다…

이때는 재귀를 이용해서 풀었는데, 사전순으로 가장 앞에 오는 문자부터 체크해서 그 문자의 index부터 시작해도 각 문자를 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 ''