316. Remove Duplicate Letters

'''
Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
'''
'''
last_occ = used to capture last occurence of any character in string

We traverse sequentially on the string
1.For each s[i], we check whether it's already in stack or not
2.if its not in the stack, we need to push it to the stack. But we need to check another condition before pushing.
3.If s[i] is not in the stack (we can check using this in O(1) using a set), and it is smaller than previous elements in stack (lexicographically), and those elements are repeating in future (can check with last_occ), we need to pop these elements
4.Now we can push s[i] in stack
5.Finally just join the characters in stack to form the result
'''
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        last=defaultdict(int)
        for i,j in enumerate(s):
            last[j]=i
        st=[]

        vis,n=set(),len(s)
        for i in range(n):
            if s[i] not in vis:
                while st and st[-1]>s[i] and last[st[-1]]>i:
                    vis.remove(st.pop())
                st.append(s[i])
                vis.add(s[i])
        return ''.join(st)