Smallest Subsequence of Distinct Characters - Solution & Explanation
Problem Statement
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 <= 1000sconsists of lowercase English letters.
Note: This question is the same as 316: https://leetcode.com/problems/remove-duplicate-letters/
Approach Overview
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 1: Stack-based Approach
This approach utilizes a stack to build the smallest lexicographical subsequence. We ensure that each character appears only once by popping the top of the stack if it's greater than the current character and can appear later in the string.
The code uses a stack to keep track of characters and ensures no duplicates by using a boolean array. The last occurrences of characters are stored in an array to decide if a character in the stack can still appear later.
Complexity
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1) (excluding the output), as the alphabet size is constant.
Approach 2: Greedy Algorithm with Counting
This approach involves using a count of characters while greedily constructing the result by iteratively checking character positions and ensuring minimal lexicographical ordering.
This method keeps a count of characters to ensure each is used exactly once and greedily appends to the result string while preserving lexicographical order.
Complexity
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1) (excluding the output), due to fixed character set size.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Stack-based Approach | Time Complexity: O(n), where n is the length of the string. |
| Greedy Algorithm with Counting | Time Complexity: O(n), where n is the length of the string. |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
remove duplicate letters | leetcode 316 | smallest subsequence of distinct characters| leetcode 1081 • Naresh Gupta • 29,147 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Smallest Subsequence of Distinct Characters easy or hard?
Smallest Subsequence of Distinct Characters Python/Java solution
How to solve Smallest Subsequence of Distinct Characters in O(n)?
What is the best approach for Smallest Subsequence of Distinct Characters?
Is Smallest Subsequence of Distinct Characters asked at Google/Amazon/Meta?
What data structure is used in Smallest Subsequence of Distinct Characters?
What is the time complexity of Smallest Subsequence of Distinct Characters?
Ready to solve this problem?
Practice Smallest Subsequence of Distinct Characters with our built-in code editor and test cases.
Practice on FleetCode