# I found it easier to think about using the rightmost position of each character.
# If we haven't added the character to the  string, and doing so would violate lexicographical order, remove all characters currently in the string that have a later # rightmost position than the current index. 
# This ensures that we have the smallest lexicographical ordering.
from collections import Counter, defaultdict

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        # Last position in string
        last = {}
        for i in range(len(s) - 1, -1, -1):
            if s[i] not in last:
                last[s[i]] = i


        final = []
        seen = defaultdict(bool)
        for i, char in enumerate(s):
            # However, we should only do that processing when we need to add a new 
            # character. Otherwise we could prematurely delete something.
            if not seen[char]:
                # insight: if there exists the letter later on, and we violate
                # lexicographical ordering, we should remove it.
                while final and final[-1] > char and last[final[-1]] > i:
                    seen[final[-1]] = False
                    final.pop()
                final.append(char)
                seen[char] = True
        
        return ''.join(final)