🔊
파이썬 알고리즘 인터뷰
책을 참고했습니다.
문자열 s가 주어지면 모든 문자가 한 번만 나타나도록 중복 문자를 제거합니다. 결과가 가능한 모든 결과 중에서 사전 식 순서로 가장 작은 지 확인해야합니다.
중복문자를 제거하고 사전식으로 정렬한다는 말이 어렵다.
여기서 사전식으로 정렬의 의미는 중복된 문자를 제거하되 마지막 한개 남은 문자라면 그냥 남겨 두고 뒤에 중복문자가 있는 문자라면 앞에 이미 들어가 있는 중복문자를 삭제하고 현재 문자를 스택에 넣어서 정렬한다는 의미다.
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
strset = set(s)
stack, counter = [], collections.Counter(s)
for ch in s:
counter[ch] -= 1
if ch in stack:
continue
while stack and ch < stack[-1] and counter[stack[-1]] > 0:
stack.pop()
stack.append(ch)
return ''.join(stack)