How do you solve Smallest Subsequence of Distinct Characters on LeetCode?

Smallest Subsequence of Distinct Characters (LeetCode #1081) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Greedy algorithms can often yield optimal solutions for problems involving order and uniqueness.

What is the brute force solution for Smallest Subsequence of Distinct Characters?

The brute force approach for Smallest Subsequence of Distinct Characters is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach generates all possible subsequences of the string and checks which ones contain all distinct characters. It then selects the lexicographically smallest one. This method is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Smallest Subsequence of Distinct Characters?

Smallest Subsequence of Distinct Characters uses the following concepts: String, Stack, Greedy, Monotonic Stack. The recommended patterns to study are: Greedy, Stack, Monotonic Stack.

What are the interview tips for Smallest Subsequence of Distinct Characters?

Always clarify the problem constraints and requirements before jumping into coding. Think aloud while solving to demonstrate your thought process to the interviewer. Practice writing clean and efficient code, as readability is crucial in interviews.

What are common mistakes when solving Smallest Subsequence of Distinct Characters?

Not considering the order of characters when building the result. Failing to track character counts correctly, leading to incorrect subsequences.

#1081

Smallest Subsequence of Distinct Characters

Medium

StringStackGreedyMonotonic StackGreedyStackMonotonic Stack

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses a greedy algorithm with a stack to build the smallest subsequence. We maintain a count of characters and ensure that we only add a character if it helps in forming the smallest lexicographical order.

⚙️

Algorithm

3 steps

1Step 1: Count the occurrences of each character in the string.
2Step 2: Use a stack to build the result, ensuring each character is added only once.
3Step 3: For each character, pop from the stack if the current character is smaller and can still be found later in the string.

solution.py12 lines

1def smallestSubsequence(s):
2    stack = []
3    seen = set()
4    count = {c: s.count(c) for c in set(s)}
5    for c in s:
6        if c not in seen:
7            while stack and stack[-1] > c and count[stack[-1]] > 0:
8                seen.remove(stack.pop())
9            stack.append(c)
10            seen.add(c)
11        count[c] -= 1
12    return ''.join(stack)

ℹ

Complexity note: The time complexity is linear because we traverse the string once, and the stack operations are amortized constant time. The space complexity is linear due to the stack and character count arrays.

1Greedy algorithms can often yield optimal solutions for problems involving order and uniqueness.
2Using a stack can help maintain order while allowing for efficient checks and modifications.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.