from typing import List
from collections import Counter
class Solution:
def removeDuplicateLettersRecur(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 ''
def removeDuplicateLettersStack(self, s: str) -> str:
counter, seen, stack = Counter(s), set(), []
for char in s:
counter[char] -= 1
if char in seen:
continue
while stack and char < stack[-1] and counter[stack[-1]] > 0:
seen.remove(stack.pop())
stack.append(char)
seen.add(char)
return ''.join(stack)