# Stack: LeetCode 316 remove duplicate letters

## 316. Remove Duplicate Letters

`class Solution:    def removeDuplicateLetters(self, s: str) -> str:        last_occur = {ch:i for i, ch in enumerate(s)}        stack = ["!"]        visited = set()        for i, ch in enumerate(s):            if ch in visited:continue            while ch < stack[-1] and last_occur[stack[-1]] > i:                visited.remove(stack.pop())            stack.append(ch)            visited.add(ch)        return "".join(stack[1:])`
1. Initialize our `stack` either as empty or with a symbol, which is less than any letter ('!' in my case), so we do not need to deal with the case of the empty stack. Also, initialize `Visited` as an empty set.
2. Iterate over our string and if we already have a symbol in `Visited`, we just continue.
3. Then, we try to remove elements from the top of our stack: we do it if the new symbol is less than the previous and also if the last occurrence of the last symbol is more than `i`: it means that we have removed symbol later in our string, so if we remove it we will not fail to construct full string.
4. Append a new symbol to our stack and mark it as visited.
5. Finally, return string built from our stack.

Data Scientist/MLE/SWE @takemobi

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi