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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Smallest Subsequence of Distinct Characters

Difficulty: Medium

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

  • The result must contain all distinct characters from the input string.
  • The order of characters in the result should be lexicographically smallest.
  • A greedy approach can be used to build the result by ensuring that at each step, the smallest possible character is selected.
  • A stack can help maintain the order of characters while ensuring that duplicates are not added.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input string s. Each character is processed a limited number of times. Space Complexity: O(1), since the maximum number of distinct characters is limited (26 lowercase English letters).

Solution

We can use a stack to build the result string. The algorithm maintains a set to track the characters that are in the stack. For each character in the string, we check if it can be added to the stack. If the current character is smaller than the character at the top of the stack and the top character appears later in the string, we pop the stack. This ensures that we always maintain the lexicographical order. Once done, we concatenate the characters in the stack to form the final result.

Code Solutions

def smallestSubsequence(s: str) -> str:
    stack = []
    seen = set()  # To keep track of the characters in the stack
    last_occurrence = {char: i for i, char in enumerate(s)}  # Last occurrence of each character

    for i, char in enumerate(s):
        if char in seen:
            continue
        # Ensure the stack maintains the smallest lexicographical order
        while stack and stack[-1] > char and i < last_occurrence[stack[-1]]:
            seen.remove(stack.pop())
        stack.append(char)
        seen.add(char)

    return ''.join(stack)
← Back to All Questions