[리트코드] 1081 - Smallest Subsequence of Distinct Characters

1081. Smallest Subsequence of Distinct Characters

Medium

---

Given a string s, 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"

 

Constraints:

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

 

Note: This question is the same as 316: https://leetcode.com/problems/remove-duplicate-letters/

분류

문자열, 스택, 그리디, 단조 스택

---

문제 풀이

문제 분석

주어진 문자열 s에서 모든 고유한 문자를 정확히 한 번씩 포함하는 가장 작은 부분 수열을 반환하는 문제입니다. 여기서 "가장 작은"은 사전식 순서(lexicographically smallest)를 의미합니다. 즉, 결과 문자열이 가능한 한 앞쪽에 위치해야 합니다.

• 입력: 문자열 s (소문자 영어 알파벳으로 구성, 길이 1 이상 1000 이하)
• 출력: s의 모든 고유 문자를 한 번씩 포함하는 사전식으로 가장 작은 부분 수열

접근 방법

이 문제는 그리디(Greedy) 알고리즘과 스택(Stack) 자료구조를 사용하여 해결할 수 있습니다. 사전식으로 가장 작은 부분 수열을 만들기 위해서는 가능한 한 앞쪽에서 작은 문자를 선택해야 합니다. 하지만 단순히 앞에서부터 문자를 선택하면 모든 고유 문자를 포함하지 못하거나, 나중에 더 작은 문자를 선택할 기회를 놓칠 수 있습니다.

따라서, 문자를 순회하면서 현재 문자를 결과에 추가할지 말지를 결정하는데, 이때 스택을 활용하여 기존에 선택된 문자들과 비교합니다. 스택의 맨 위 문자가 현재 문자보다 크고, 그 문자가 문자열 s의 더 뒤쪽에도 남아있다면, 스택의 맨 위 문자를 제거하여 더 작은 문자를 앞으로 배치할 수 있는 기회를 만듭니다.

구현 설명

1. 문자 빈도수 및 결과 저장 자료구조 초기화

• str_counts = Counter(s): 입력 문자열 s에 포함된 각 문자의 빈도수를 계산하여 Counter 객체에 저장합니다. 이는 나중에 특정 문자가 결과에서 제거되었을 때, 해당 문자가 문자열 s의 뒤쪽에 더 있는지 여부를 확인하는 데 사용됩니다.
• answer = []: 최종 결과를 저장할 리스트입니다. 스택처럼 사용될 것입니다.
• answer_set = set(): answer 리스트에 이미 추가된 문자를 빠르게 확인하기 위한 집합(set)입니다. 중복 추가를 방지합니다.

2. 문자 순회 및 스택 관리

• for x in s:: 입력 문자열 s의 각 문자 x에 대해 반복합니다.
• if x in answer_set: ... continue: 만약 현재 문자 x가 이미 answer_set에 있다면 (즉, 결과에 이미 포함되어 있다면), 해당 문자의 str_counts를 1 감소시키고 다음 문자로 넘어갑니다.
• while answer and answer[-1] > x and str_counts[answer[-1]] > 0:: 이 부분이 핵심입니다.
  • answer가 비어있지 않고,
  • 스택의 맨 위 문자(answer[-1])가 현재 문자 x보다 크고,
  • 스택의 맨 위 문자가 문자열 s의 더 뒤쪽에도 남아있는 경우(str_counts[answer[-1]] > 0),
  • 스택의 맨 위 문자는 제거될 수 있습니다. 왜냐하면 현재 문자 x가 더 작고, 나중에 제거된 문자를 다시 추가할 수 있는 기회가 있기 때문입니다.
  • answer_set.remove(answer[-1]): answer_set에서도 제거합니다.
  • answer.pop(): 스택에서 맨 위 문자를 제거합니다.
• answer.append(x): 위 while 루프가 끝나면 (더 이상 제거할 문자가 없거나 조건이 맞지 않으면), 현재 문자 x를 answer 리스트에 추가합니다.
• answer_set.add(x): answer_set에도 추가합니다.
• str_counts[x] -= 1: 현재 문자 x가 결과에 추가되었으므로, str_counts를 1 감소시켜 남은 빈도수를 업데이트합니다.

3. 결과 반환

• return "".join(answer): 최종적으로 answer 리스트에 저장된 문자들을 순서대로 합쳐 하나의 문자열로 반환합니다.

⏱복잡도 분석

• 시간 복잡도: O(N), 여기서 N은 문자열 s의 길이입니다.

  • 문자열 s를 한 번 순회합니다.
  • Counter(s)는 O(N)입니다.
  • while 루프 안에서의 pop() 연산은 각 문자가 스택에 최대 한 번 추가되고 최대 한 번 제거되므로, 전체적으로 모든 문자에 대해 상수 번의 연산만 수행합니다.
  • set 연산(in, add, remove)은 평균적으로 O(1)입니다.
  • 따라서 전체 시간 복잡도는 O(N)입니다.

• 공간 복잡도: O(K), 여기서 K는 문자열 s에 포함된 고유 문자의 개수입니다. (알파벳의 경우 최대 26)

  • str_counts: 최대 26개의 키를 가집니다.
  • answer: 최대 26개의 요소를 가집니다.
  • answer_set: 최대 26개의 요소를 가집니다.
  • 따라서 공간 복잡도는 O(K)이며, 입력 문자열의 길이 N과는 독립적으로 상수 공간에 가깝습니다 (알파벳의 경우).

핵심 포인트

1. 사전식 순서 유지: 가장 작은 부분 수열을 만들기 위해, 현재 문자가 스택의 맨 위 문자보다 작다면, 스택의 맨 위 문자를 제거할 수 있는지 항상 확인해야 합니다.
2. 문자 재등장 가능성: 스택에서 문자를 제거할 때는 해당 문자가 문자열 s의 뒤쪽에 더 이상 존재하지 않는다면 제거하면 안 됩니다. str_counts를 사용하여 이를 확인합니다.
3. 단조 스택 활용: 문제 해결 과정에서 스택은 항상 오름차순(사전식으로)으로 정렬된 상태를 유지하려는 경향을 보입니다. 이는 단조 스택(Monotonic Stack)의 특징입니다.

풀이 코드

from collections import Counter

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        str_counts = Counter(s)
        answer = []
        answer_set = set()
        for x in s:
            if x in answer_set:
                str_counts[x] -= 1
                continue

            while answer and answer[-1] > x and str_counts[answer[-1]] > 0:
                answer_set.remove(answer[-1])
                answer.pop()
                
            answer.append(x)
            answer_set.add(x)
            str_counts[x] -= 1

        return "".join(answer)