Is Smallest Subsequence of Distinct Characters easy or hard?

The problem is classified as Medium difficulty on most coding platforms. The challenge is recognizing the greedy condition for removing characters and implementing it using a monotonic stack. Once the pattern is known, the implementation is straightforward and runs in linear time.

Smallest Subsequence of Distinct Characters Python/Java solution

Both Python and Java implementations follow the same logic: maintain a stack, track remaining character counts, and record whether a character is already in the result. During iteration, pop larger characters that still appear later and push the current character if it has not been used. This results in an O(n) time solution suitable for large inputs.

How to solve Smallest Subsequence of Distinct Characters in O(n)?

Scan the string while maintaining a stack for the current subsequence and a frequency count of remaining characters. If the current character is smaller than the stack top and the top character appears later again, pop it from the stack. Add the current character only if it is not already included. This greedy stack process ensures each character appears once and produces the lexicographically smallest result in O(n) time.

What is the best approach for Smallest Subsequence of Distinct Characters?

The monotonic stack approach is the most efficient and commonly expected solution. It processes the string once while maintaining a stack that keeps characters in lexicographically increasing order. By removing larger characters that appear later, it guarantees the smallest valid subsequence. The time complexity is O(n) with constant auxiliary space for the alphabet.

Is Smallest Subsequence of Distinct Characters asked at Google/Amazon/Meta?

This pattern appears frequently in interviews at large tech companies because it tests greedy reasoning and stack usage. Variants of the problem have been reported in interviews at companies like Amazon and Google, often under topics such as monotonic stack or lexicographically smallest sequence problems.

What data structure is used in Smallest Subsequence of Distinct Characters?

A stack is the core data structure. It stores the characters of the current candidate subsequence while allowing efficient removal of larger characters that appear earlier. Additional arrays or hash sets track character frequencies and whether a character is already present in the stack.

What is the time complexity of Smallest Subsequence of Distinct Characters?

The optimal solution runs in O(n) time where n is the length of the string. Each character is pushed to and popped from the stack at most once. Frequency counting and membership checks are constant time, giving linear complexity overall with O(1) extra space for lowercase characters.

Description Hints 1 Solution Video 9:25

1081. Smallest Subsequence of Distinct Characters

Medium70.6% acceptance5 companies

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/

Asked at 5 companies

FactSet Bytedance Amazon

Google Meta

Topics

Hints open one at a time

Hint 1

Greedily try to add one missing character. How to check if adding some character will not cause problems ? Use bit-masks to check whether you will be able to complete the sub-sequence if you add the character at some index i.

9:25

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution