Remove Duplicates Letters

#Solution 1
count = Counter(s) # initialize frequency hashmap
st = []
taken = set()
for char in s:
	if char not in taken:
		# check if there are any more instances of the evicting character
		while st and st[-1] > char and count[st[-1]] > 0:
			taken.remove(st.pop())
		st.append(char)
		taken.add(char)
	count[char] -= 1 # finish processing this character
return ''.join(st)

#Solution 2: Another solution written in slightly different way
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        stack = []
        
        for idx, character in enumerate(s):
            if not stack:
                stack.append(character)
            elif character in stack:
                continue
            else:
                while stack and (character < stack[-1]):
                    if stack[-1] in s[idx + 1:]:
                        _ = stack.pop()
                    else:
                        break
                        
                stack.append(character)
                
        return ''.join(stack)