a guest Jan 18th, 2020 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from collections import defaultdict
  2. class Solution:
  3.     def removeDuplicateLetters(self, s: str) -> str:
  4.         charToLoc = defaultdict(list)
  5.         for i, c in enumerate(s):
  6.             charToLoc[c].append(i)
  8.         def f(path, remaining):
  9.             if not remaining:
  10.                 yield ''.join(s[i] for i in path)
  11.             else:
  12.                 # Take smallest letter possible as early as possible
  13.                 for c in sorted(remaining):
  14.                     for loc in charToLoc[c]:
  15.                         if not path or loc > path[-1]:
  16.                                 path.append(loc)
  17.                                 remaining.remove(c)        
  18.                                 # check that all other characters still have something that can be used                      
  19.                                 if all(loc < charToLoc[other][-1] for other in remaining):
  20.                                     yield from f(path, remaining)
  21.                                 remaining.add(c)
  22.                                 path.pop()
  24.         return next(f([], set(s)))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand