📌 Problem.

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

알파벳으로만 구성된 문자열 s가 주어진다.
s 내에 중복되는 알파벳들을 하나씩만 남기는 방법은 여러 가지가 있다.
그 중 사전식으로 가장 작은 문자열을 반환하는 함수를 작성하는 문제이다.

가령 'babc'는 'bac', 'abc'가 될 수 있는데, 그 중 'abc'를 반환해야 한다.

📌 Solution.

1. 재귀

def removeDuplicateLetters(self, s: str) -> str:
    for ch in sorted(set(s)):
        part = s[s.index(ch):]
        if set(s) == set(part):
            return ch + self.removeDuplicateLetters(part.replace(ch, ''))
    return ''

가능한 가장 작은 알파벳을 앞에서부터 채워나가는 방식이다.
set(s) == set(part)의 의미를 이해하는 것이 핵심이다.
part가 원래 문자열에 있는 알파벳들을 적어도 한 번씩은 사용했는지 검사하는 구문이다.

가령 s가 'bbac'라고 하면 첫번째 part는 'ac'가 되는데, 알파벳 b가 들어 있지 않으므로 활용할 수 없다.
다음 part는 'bbac'가 되며, 알파벳 a, b, c를 한 번씩 모두 사용하므로 b 하나만을 취하고 'ac'를 넘겨 재귀 함수를 호출하면 된다.

2. 스택

def removeDuplicateLetters(self, s: str) -> str:
    counter = collections.Counter(s)
    used = set()
    stack = []  # result

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

for문 내 while문의 의미를 이해하는 것이 핵심이다.
stack[-1], 즉 tos(top of stack)에 있는 알파벳이 s의 뒤에 더 존재하고, 현재 추가하려는 알파벳 ch보다 크면 계속해서 stack, used에서 tos를 제거하는 구문이다.

1번 풀이는 가능한 가장 작은 알파벳들부터 하나씩 채워가는 풀이였다면, 2번 풀이는 중복만 없으면 일단 알파벳을 추가하되, 조건에 따라 알파벳을 다시 제거하며 다시 채워나가는 풀이라고 할 수 있다.