mediumStack / QueuePure DSA~35 min
Smallest Subsequence With Each Letter Once
Compress a string so every distinct letter appears exactly once, choosing the lexicographically smallest possible result while preserving feasibility.
Problem
Given a string s, remove duplicate letters so that every letter appears exactly once and the result is the smallest in lexicographical order among all such unique-letter subsequences. Return that string.
Input
A string s of lowercase English letters.
Output
The lexicographically smallest unique-letter subsequence.
Constraints
- 1 <= s.length <= 10^4
- s consists of lowercase English letters.
Examples
Example 1
Input
s = "bcabc"
Output
"abc"
Each letter once, smallest order.
Example 2
Input
s = "cbacdcbc"
Output
"acdb"
Greedy monotonic stack yields the smallest valid arrangement.