from collections import defaultdict
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        charToLoc = defaultdict(list)
        for i, c in enumerate(s):
            charToLoc[c].append(i)

        def f(path, remaining):
            if not remaining:
                yield ''.join(s[i] for i in path)
            else:
                # Take smallest letter possible as early as possible
                for c in sorted(remaining):
                    for loc in charToLoc[c]:
                        if not path or loc > path[-1]:
                                path.append(loc)
                                remaining.remove(c)
                                # check that all other characters still have something that can be used
                                if all(loc < charToLoc[other][-1] for other in remaining):
                                    yield from f(path, remaining)
                                remaining.add(c)
                                path.pop()

        return next(f([], set(s)))