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.