Watch 10 video solutions for Smallest Subsequence of Distinct Characters, a medium level problem involving String, Stack, Greedy. This walkthrough by Naresh Gupta has 28,639 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1000s consists of lowercase English letters.Note: This question is the same as 316: https://leetcode.com/problems/remove-duplicate-letters/
Problem Overview: Given a string s, return the lexicographically smallest subsequence that contains every distinct character exactly once. You can delete characters but must preserve relative order. The challenge is choosing which occurrences to keep so the final sequence is both unique and minimal in lexicographic order.
Approach 1: Brute Force with Subsequence Checking (Exponential Time)
The naive idea is to generate subsequences of the string and filter those that contain all unique characters exactly once. Among valid candidates, select the lexicographically smallest. This approach quickly becomes impractical because a string of length n has 2^n subsequences. Even with pruning using sets to track distinct characters, the worst‑case time complexity remains O(2^n) with O(n) auxiliary space. This method mainly helps understand the problem constraints before optimizing.
Approach 2: Monotonic Stack (O(n) time, O(1) space)
The optimal approach uses a stack to maintain the current best subsequence while scanning the string once. First count how many times each character appears. While iterating through the string, push characters onto the stack only if they are not already included. Before pushing, compare the current character with the top of the stack. If the stack top is lexicographically larger and appears again later in the string, you can safely pop it to build a smaller result. This creates a monotonic stack that keeps the subsequence lexicographically minimal. A boolean array tracks whether a character is already used. The algorithm runs in O(n) time since each character is pushed and popped at most once, and uses O(1) space for the fixed alphabet.
Approach 3: Greedy with Frequency Counting (O(n) time, O(1) space)
This method expresses the same idea in a greedy framework. Track remaining character frequencies and maintain a result structure similar to a stack. When processing a new character, decrement its remaining count. If the character already exists in the result, skip it. Otherwise, repeatedly remove the last character if it is larger than the current one and still appears later. This greedy rule guarantees the smallest possible prefix while ensuring all characters remain available. The implementation relies on constant‑time membership checks and frequency arrays, making it efficient for large strings. It naturally combines ideas from greedy algorithms and stack processing.
Recommended for interviews: The monotonic stack solution is what interviewers expect. It demonstrates control over greedy reasoning, stack operations, and frequency tracking. Mentioning the brute force idea shows understanding of the search space, but implementing the O(n) stack-based approach proves you can optimize string problems effectively.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subsequence Enumeration | O(2^n) | O(n) | Conceptual understanding or very small inputs |
| Monotonic Stack | O(n) | O(1) | Best general solution for interviews and production |
| Greedy with Frequency Counting | O(n) | O(1) | Alternative implementation using greedy reasoning |