433. Smallest Distinct Subsequence
A sign painter has a long strip of lowercase letters and wants a short plaque that shows every different letter of the strip exactly once. The plaque must be cut from the strip by deleting some letters, so the surviving letters keep the same left-to-right order they had on the strip.
Given the string s, return the plaque text that is smallest in dictionary order among all strings that contain each distinct letter of s exactly once and can be obtained by deleting characters from s. For the empty string the answer is the empty string. The strip can be as long as 100,000 letters.
Example 1
- Input:
- s = "dbdaecbe"
- Output:
- "bdace"
- Explanation:
The letters b, d, a, e, c are needed. The first d can be dropped because another d comes later, so b leads; starting with a is impossible because d and b would be lost. The best plaque is
"bdace".
Example 2
- Input:
- s = "qpqqrpr"
- Output:
- "pqr"
- Explanation:
The letters q, p, r are needed. Both later q letters keep q available, so the leading q can be dropped and p goes first, then q, then r, giving
"pqr".
Constraints
0 ≤ s.length ≤ 105
s consists of lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)