Stack: LeetCode 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