Smallest Distinct-Letter Subsequence
MediumStack
Problem
Given a string s of lowercase letters, choose a subsequence (keep characters in their original order, possibly skipping some) that contains every distinct letter of `s` exactly once.
Among all such subsequences, return the lexicographically smallest one.
Example 1
- Input:
- s = "dcadcb"
- Output:
- "adcb"
There is only one a, at index 2. After it come d, c, b once each, in that order.
Example 2
- Input:
- s = "bab"
- Output:
- "ab"
Skip the first b and keep a, b.
Constraints
- 1 ≤ s.length ≤ 10^5
- s contains only lowercase English letters
Hint
Show the first hint
Build the answer left to right. When is it safe to discard a letter you already placed?
Walkthrough
How to approach it
01Clarify before coding
- Each distinct letter exactly once? Yes, no letter may be missing or repeated.
- Subsequence, not substring? Yes, characters may be skipped.
- Only lowercase letters? Yes, so the answer has at most 26 letters.
02Brute force
Enumerate subsequences with each distinct letter once and keep the smallest.
Cost: Exponential in the number of repeated letters.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.