#1081

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Smallest Subsequence of Distinct Characters

The Smallest Subsequence of Distinct Characters problem asks you to find the lexicographically smallest subsequence of a string with distinct characters.

string stack greedy monotonic stack

Problem Statement

You are given a string s consisting of lowercase English letters. Your task is to return the lexicographically smallest subsequence of s that contains all distinct characters from s exactly once.

The result should maintain the relative order of the characters from the original string while ensuring no character is repeated. You must optimize your solution to handle strings of length up to 1000.

Examples

Example 1

Input: s = "bcabc"

Output: "abc"

Example details omitted.

Example 2

Input: s = "cbacdcbc"

Output: "acdb"

Example details omitted.

Constraints

1 <= s.length <= 1000
s consists of lowercase English letters.

Solution Approach

Greedy with Stack-based State Management

Use a stack to maintain the smallest lexicographical order by iterating over the string and adding characters to the stack greedily. Pop characters from the stack when a smaller character is found and the removed character can still appear later in the string.

Track Occurrences and Lexicographical Order

While iterating, keep track of the last occurrences of characters to know when it is safe to pop characters from the stack. Use a greedy approach to ensure that you add characters in the smallest order possible without violating constraints.

Efficient Stack-based Iteration

Iterate through the string while using a stack to maintain order and a bitmask or frequency counter to track characters that still need to be added. Ensure that each character is added only once, and the smallest lexicographical sequence is formed.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n), where n is the length of the string. This is due to the single pass through the string and constant-time operations for stack manipulation. The space complexity is O(k), where k is the number of distinct characters in the string, as we only store a limited number of elements in the stack and frequency table.

What Interviewers Usually Probe

Look for a solution that efficiently uses a stack to maintain order.
Ensure that the candidate tracks character occurrences and pops characters from the stack when appropriate.
Candidates should avoid brute-force solutions and focus on a greedy, stack-based approach.

Common Pitfalls or Variants

Common pitfalls

Failing to check if a character can still appear later, which can result in an incorrect subsequence.
Not managing the stack in lexicographical order, leading to suboptimal solutions.
Inefficient handling of character occurrences, which may lead to unnecessary operations and higher time complexity.

Follow-up variants

Handle the case where the string contains all unique characters.
Optimize for strings with large character repetitions.
Extend the solution to handle strings with uppercase letters or non-alphabetic characters.

FAQ

What is the key pattern in the Smallest Subsequence of Distinct Characters problem?

The key pattern is stack-based state management, where a stack is used to maintain the lexicographically smallest subsequence by greedily adding characters.

How can I optimize my solution for strings with many repeated characters?

Optimize by using a frequency counter or bitmask to track characters that still need to be added, allowing efficient stack operations.

How does greedy decision-making affect the result?

Greedy decisions ensure that you always choose the smallest possible character that can still complete the subsequence while maintaining order.

Why is stack-based state management essential for this problem?

Stack-based state management ensures that the subsequence maintains lexicographical order while efficiently handling additions and removals of characters.

What common mistake should I avoid in this problem?

A common mistake is not managing character occurrences properly, which could lead to incorrect subsequences or inefficient solutions.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        last = {c: i for i, c in enumerate(s)}
        stk = []
        vis = set()
        for i, c in enumerate(s):
            if c in vis:
                continue
            while stk and stk[-1] > c and last[stk[-1]] > i:
                vis.remove(stk.pop())
            stk.append(c)
            vis.add(c)
        return "".join(stk)

Solution 2

#### Java

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        last = {c: i for i, c in enumerate(s)}
        stk = []
        vis = set()
        for i, c in enumerate(s):
            if c in vis:
                continue
            while stk and stk[-1] > c and last[stk[-1]] > i:
                vis.remove(stk.pop())
            stk.append(c)
            vis.add(c)
        return "".join(stk)

Continue Practicing

#402 remove k digits #316 remove duplicate letters #1130 minimum cost tree from leaf values