We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Smallest Subsequence of Distinct Characters

Number: 1159

Difficulty: Medium

Paid? No

Companies: Oracle, Meta, FactSet, Google, Amazon, ByteDance

Problem Description

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

Key Insights

  • Each unique character must appear exactly once in the result.
  • The selected subsequence should be lexicographically smallest.
  • Utilize a monotonic stack to maintain order and allow removal of characters that can appear later.
  • Maintain a frequency counter to decide if it is safe to remove a character from the current sequence.
  • Use a greedy strategy: for every character, remove all previous characters that are lexicographically larger and still available later.

Space and Time Complexity

Time Complexity: O(n) as we process each character in the string once. Space Complexity: O(n) for the stack and auxiliary data structures (frequency counter and set).

Solution

The solution leverages a greedy algorithm along with a monotonic stack. First, count the occurrences of every character in the string. Then, iterate over the string and for each character:

  1. Decrement its count.
  2. Skip the character if it is already in the result (tracked via a set).
  3. Remove characters from the stack that are greater than the current character and that will appear again later (their frequency is still positive).
  4. Add the current character to the stack. At the end, the stack represents the lexicographically smallest subsequence containing distinct characters exactly once.

Code Solutions

# Python solution for Smallest Subsequence of Distinct Characters

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        # Create a counter for each character in s
        char_count = {}
        for char in s:
            char_count[char] = char_count.get(char, 0) + 1
        
        stack = []  # Monotonic stack to build the result
        in_stack = set()  # Set to keep track of characters in the stack

        # Process each character in the string
        for char in s:
            # Decrease count since this character is being processed
            char_count[char] -= 1
            
            # If the character is already in the stack, skip it
            if char in in_stack:
                continue
            
            # Remove characters that are larger than current char and can appear later
            while stack and stack[-1] > char and char_count[stack[-1]] > 0:
                removed_char = stack.pop()
                in_stack.remove(removed_char)
            
            # Add current character to the stack and mark it as seen
            stack.append(char)
            in_stack.add(char)
        
        # Return the joined characters in the stack as the final answer
        return "".join(stack)
← Back to All Questions