316. Remove Duplicate Letters

Jul 6th, 2022
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.29 KB | None | 0 0
  1. '''
  2. Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
  3. '''
  4. '''
  5. last_occ = used to capture last occurence of any character in string
  7. We traverse sequentially on the string
  8. 1.For each s[i], we check whether it's already in stack or not
  9. 2.if its not in the stack, we need to push it to the stack. But we need to check another condition before pushing.
  10. 3.If s[i] is not in the stack (we can check using this in O(1) using a set), and it is smaller than previous elements in stack (lexicographically), and those elements are repeating in future (can check with last_occ), we need to pop these elements
  11. 4.Now we can push s[i] in stack
  12. 5.Finally just join the characters in stack to form the result
  13. '''
  14. class Solution:
  15.     def removeDuplicateLetters(self, s: str) -> str:
  16.         last=defaultdict(int)
  17.         for i,j in enumerate(s):
  18.             last[j]=i
  19.         st=[]
  21.         vis,n=set(),len(s)
  22.         for i in range(n):
  23.             if s[i] not in vis:
  24.                 while st and st[-1]>s[i] and last[st[-1]]>i:
  25.                     vis.remove(st.pop())
  26.                 st.append(s[i])
  27.                 vis.add(s[i])
  28.         return ''.join(st)        
Add Comment
Please, Sign In to add comment