# 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:])`

The explanation is from Here.

Let us try to build our answer in a greedy way: we take letter by letter and put them into the stack: if we have the next letter which decreased the lexicographical order of the string, we remove it from the stack and put the new letter. However we need to be careful: if we remove some letters from the stack and it was the last occurrence, then we failed: we can not finish this process. So, we need to do the following:

1. Find `last_occ`: last occurrences for each letter in our string
2. 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.
3. Iterate over our string and if we already have a symbol in `Visited`, we just continue.
4. 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.
5. Append a new symbol to our stack and mark it as visited.
6. Finally, return string built from our stack.

Complexity: Time complexity is `O(n)`because we iterate our string once. Space complexity is `O(26)`because it will be the longest size of our stack and answer.

--

--