1081. Smallest Subsequence of Distinct Characters

Medium

---

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/

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        stack = []
        indexes = {}
        visited = set()
        for index, char in enumerate(list(s)):
            indexes[char] = index
        for index, char in enumerate(list(s)):
            if char not in visited:
                while stack and stack[-1] > char and index < indexes[stack[-1]]:
                    c = stack.pop()
                    visited.remove(c)
                stack.append(char)
                visited.add(char)
        return ''.join(stack)