Skip to content

1081. Smallest Subsequence of Distinct Characters

Difficulty Topics

Description

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

smallest-subsequence-of-distinct-characters.py
class Solution:
    def smallestSubsequence(self, s: str) -> str:
        stack = []
        put = set()
        counter = Counter(s)

        for x in s:
            counter[x] -= 1

            if x in put: continue

            while stack and x < stack[-1] and counter[stack[-1]] > 0:
                put.remove(stack.pop())

            stack.append(x)
            put.add(x)

        return "".join(stack)