Domain 2MediumMEDIUM

Smallest Subsequence of Distinct Characters

Construct the lexicographically smallest subsequence by greedily maintaining a monotonic increasing stack while ensuring all distinct characters are included.

Domain: medium•Updated: 2026-09-08
#monotonic stack#hash map#greedy algorithm

Problem Breakdown

We need to find a subsequence of s that includes every unique character present in the string exactly once. Among all such valid subsequences, we must return the one that is lexicographically smallest (comes first alphabetically).

Key Constraints:

  1. Subsequence: Relative order from original string must be preserved; no reordering allowed.
  2. Distinctness: Each unique character in s appears exactly once in the result, regardless of how many times it appeared in s.
  3. Lexicographical Order: We prioritize smaller characters appearing earlier in our output.

Intuition

A brute-force approach generating all subsequences is exponential (O(2N)O(2^N)). Instead, we can use a greedy strategy with backtracking capabilities via a stack:

  1. Greedy Choice: Always try to place the smallest available character as early as possible.
  2. Backtracking (Stack Popping): If our current result ends with a larger character than the new incoming character c, and that larger character appears again later in s (so we can add it back safely), we should remove the larger character from our stack to place c earlier for lexicographical gain.
  3. Tracking: We need to know if characters appear later (last_occurrence) so we don’t discard a necessary unique instance prematurely, and we use a set/boolean array to track which characters are currently in our subsequence (to ensure distinctness).

Approach

  1. Preprocessing: Calculate the last index of every character in s. This allows us to determine if a popped character can be re-added later.
  2. Stack Construction: Iterate through string s with an index i:
    • If current char is already included (in our stack), skip it for now. We only care about the first instance we keep, unless that specific instance was removed from the stack due to a smaller character coming up later.
    • Optimization Check: While the top of the stack contains a character larger than current_char AND that top character appears again in the string after index i:
      • Pop the stack (remove it).
      • Mark as not visited so we can add it back later.
    • Add current char to stack and mark as visited.
  3. Result: Join the characters remaining in the stack at the end of iteration.

Complexity Analysis

  • Time Complexity: O(N)O(N), where NN is the length of string s. We traverse the string once. Each character enters the stack exactly once and leaves it at most once (amortized constant time per operation). Dictionary lookups are O(1)O(1).
  • Space Complexity: O(K)O(K), where KK is the size of the alphabet (26 for lowercase English letters). We use a map for last occurrences (O(K)O(K)), a set for visited characters (O(K)O(K)), and a stack that holds at most all unique characters (O(K)O(K)). Since KK is constant relative to input length, this can be considered O(1)O(1) space complexity in the context of LeetCode constraints.

Solution

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        # Map each character to its last occurrence index in the input string
        last_occurrence = {c: i for i, c in enumerate(s)}
        
        stack = []
        visited = set()  # To track characters currently included in our subsequence
        
        for i, char in enumerate(s):
            if char not in visited:
                # While the current character is smaller than the top of the stack,
                # and the top element appears later again (so we can pop it safely),
                # remove the larger element from the stack to maintain lexicographical order.
                while stack and last_occurrence[stack[-1]] > i:
                    removed_char = stack.pop()
                    visited.remove(removed_char)
                
                stack.append(char)
                visited.add(char)
        
        return "".join(stack)

# Example usage for verification (not part of the class solution):
# sol = Solution()
# print(sol.smallestSubsequence("bcabc"))   # Output: "abc"
# print(sol.smallestSubsequence("cbacdcbc")) # Output: "acdb"

Edge Cases Handled

  • Single Character Input: The loop runs once, stack gets the char, returns it. Correct.
  • All Distinct and Sorted (e.g., s = "abc"): No characters are popped because stack[-1] < current is always true or condition fails; result matches input. Correct.
  • **Duplicates Only (e.g., "aaaa")**:** First 'a' pushed, subsequent 'a's skipped by visited`. Result “a”. Correct.
  • Reverse Order with Duplicates (Example 2): Logic correctly pops larger characters from stack if they appear later in the string to accommodate smaller ones earlier.