Stack: LeetCode 316 remove duplicate letters

316. Remove Duplicate Letters

2 min readOct 12, 2020

--

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.

Sign up to discover human stories that deepen your understanding of the world.

Free

Distraction-free reading. No ads.

Organize your knowledge with lists and highlights.

Tell your story. Find your audience.

Membership

Read member-only stories

Support writers you read most

Earn money for your writing

Listen to audio narrations

Read offline with the Medium app

--

--

No responses yet

Write a response