# 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:

- Find
`last_occ`

: last occurrences for each letter in our string - 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. - Iterate over our string and if we already have a symbol in
`Visited`

, we just continue. - 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. - Append a new symbol to our stack and mark it as visited.
- 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.