1
class Solution:
2
    def smallestSubsequence(self, s: str) -> str:
3
        # calculate the last occurence of each characters in s
4
        last_occurence = {c: i for i, c in enumerate(s)}
5

6
        stack = []
7
        # check if element is in stack
8
        instack = set()
9
        for i, c in enumerate(s):
10
            if c not in instack:
11
                # check if stack already have char larger then current char
12
                # and if char in stack will occur later again, remove that from stack
13
                while stack and stack[-1] > c and last_occurence[stack[-1]] > i:
14
                    instack.remove(stack[-1])
15
                    stack.pop()
16

17
                instack.add(c)
18
                stack.append(c)
19

20
        return "".join(stack)