Smallest Subsequence of Distinct Characters

Do NOT include sr-due, sr-interval, or sr-ease. The Spaced Repetition plugin writes these automatically after your first review.

1081. Smallest Subsequence of Distinct Characters

Difficulty: Medium | Date: 2026-07-19

Patterns: Monotonic Stack | Greedy | Hash Map Data Structures: Stack | String

Problem

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

My Approach

Started thinking about sliding window since it felt like a substring problem, but caught myself - this is a subsequence (not contiguous). Pivoted to DP/recursion next, but realized the decisions are local and greedy: at each character, decide whether to keep or toss the previous one. Used a monotonic stack to build the result greedily with a first pass to count remaining occurrences.

Key Insight

At each character, pop the stack top if the current char is smaller, the top still appears later in the string (counts[top] > 0), and the current char isn’t already in the stack. The remaining-count check is what makes it safe to discard - you can only toss a character if you’ll see it again later.

Recognizing Greedy

Ask: “Can I make a locally optimal decision at each step using only information I already have?” If yes, it’s likely greedy - not DP.

Three signals that point to greedy over DP:

1. Optimization word - “smallest”, “largest”, “minimum”, “maximum” in the output (not the input constraints)
2. Local decisions are final - once you make a choice (pop or keep), you never need to revisit it
3. No unknown future dependency - you can pre-compute what you need (e.g. remaining counts) so each decision has full information

Contrast with DP: DP is when the optimal choice at step i depends on outcomes at step j > i that you can’t know yet without trying all paths. Here, a pre-pass gives you everything - that’s the greedy tell.

Solution

from collections import Counter
 
class Solution:
    def smallestSubsequence(self, s: str) -> str:
        counts = Counter(s)
        stack = []
        for char in s:
            counts[char] -= 1
            while stack and char < stack[-1] and counts[stack[-1]] >= 1 and char not in stack:
                stack.pop()
            if char not in stack:
                stack.append(char)
        return ''.join(stack)

Complexity

• Time: O(n) - each character is pushed and popped at most once
• Space: O(k) - stack holds at most k distinct characters (k <= 26)

Prerequisites

Review Log

• 2026-07-19 [Hard] - fuzzy: initially misread as DP/recursion, count condition off (> 1 vs > 0); clicked: greedy framing, remaining-count safety check
• 2026-07-25 [Good] - fuzzy: stack[0] vs stack[-1], decrementing wrong char’s count, while loop running when char already in stack; clicked: core greedy insight solid from the start