Remove duplicate characters so every letter appears once and the result is lexicographically smallest among all valid subsequences.
Remove Duplicate Letters
gfgGiven a string s, remove some characters so that each distinct character appears exactly once in the final string. The result must be a subsequence of s and among all valid subsequences it should be the lexicographically smallest possible.
Return that smallest string.
A subsequence keeps the relative order of the remaining characters.
Input Format
- A single string
sconsisting of lowercase English letters. - You may assume
sis non-empty.
Output Format
- Return the lexicographically smallest subsequence of
sthat contains every distinct character fromsexactly once.
Constraints
1 <= s.length.scontains only lowercase English letters.- The answer must be a subsequence of
s. - Every distinct character in
smust appear exactly once in the answer.
Example 1
Input
s = "bcabc"
Output
"abc"
Explanation
The valid subsequences with all distinct letters once include "bca", "bac", and "abc". The smallest lexicographically is "abc".
Example 2
Input
s = "cbacdcbc"
Output
"acdb"
Explanation
We need one of each distinct letter: a, b, c, d. The smallest subsequence satisfying this is "acdb".
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.