Return the lexicographically smallest subsequence that contains every distinct character of the input string exactly once.
Smallest Subsequence of Distinct Characters
gfgProblem
Given a string s, build a subsequence that:
- contains every distinct character that appears in
s, exactly once - is a subsequence of
s - is the lexicographically smallest possible among all valid subsequences
A subsequence keeps the original relative order of characters, but you may remove any number of characters.
Goal
Choose characters so that every distinct letter appears once, while making the resulting string as small as possible in lexicographic order.
Input Format
- A single string
sconsisting of lowercase English letters.
Output Format
- Return the lexicographically smallest valid subsequence as a string.
Constraints
1 <= s.length <= $10^{4}$scontains only lowercase English letters- The answer must include each distinct character from
sexactly once
Example 1
Input
s = "bcabc"
Output
"abc"
Explanation
The distinct characters are {a, b, c}. Among all subsequences containing each once, "abc" is lexicographically smallest.
Example 2
Input
s = "cbacdcbc"
Output
"acdb"
Explanation
One valid subsequence is "acdb". It contains each distinct character exactly once and is lexicographically smaller than other valid choices such as "adbc".
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.