Smallest Subsequence of Distinct Characters

Given a string s, return the lexicographically smallest subsequence of s that contains all the distinct characters of s exactly once.

Example 1:

Input: s = "bcabc"
Output: "abc"

Example 2:

Input: s = "cbacdcbc"
Output: "acdb"

Constraints:

• 1 <= s.length <= 1000
• s consists of lowercase English letters.

Note: This question is the same as 316: https://leetcode.com/problems/remove-duplicate-letters/SOLUTION:

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        lastIndex = {}
        for i, c in enumerate(s):
            lastIndex[c] = i
        used = set()
        stack = []
        for i, c in enumerate(s):
            if c in used:
                continue
            while len(stack) > 0 and s[stack[-1]] > c and i < lastIndex[s[stack[-1]]]:
                curr = stack.pop()
                if s[curr] in used:
                    used.remove(s[curr])
            stack.append(i)
            used.add(c)
        return "".join(s[i] for i in stack)


# class Solution:
#     def smallestSubsequence(self, s: str) -> str:
#         n = len(s)
#         numdist = len(set(s))
#         smallest = ""
#         paths = [(s[i], [i]) for i in range(n)]
#         while len(paths) > 0:
#             curr, indexes = paths.pop()
#             if smallest:
#                 if curr < smallest and len(curr) == numdist:
#                     smallest = curr
#                     for j in range(indexes[-1] + 1, n):
#                         if s[j] not in curr:
#                             paths.append((curr + s[j], indexes + [j]))
#             elif len(curr) == numdist:
#                 smallest = curr
#         return smallest