Every Letter Once

Medium

You get a string text of lowercase English letters. Strike out some letters so that every letter that occurs in text is left exactly once. The remaining letters keep their order. Among all possible results, return the lexicographically smallest one.

Example 1

text="dbcbad" → 'bcad'

We must keep one each of a, b, c and d. "bcad" can be obtained by striking letters out and is smaller than any other option: "abcd" is impossible because neither b nor c appears after the a.

Example 2

text="zzaz" → 'az'

We can get "za" or "az"; the latter is smaller.

Example 3

text="q" → 'q'

Constraints

1 ≤ len(text) ≤ 10⁴
text consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Greedy String Monotonic Stack

Similar problems

Erase Digits for the Smallest Number Medium One Bead of Each Color Medium Smallest Pick With a Required Letter Hard Smallest Up-Down Sequence Medium Fix the Middle of the Line Medium

Input

text="dbcbad"

Expected

'bcad'

Run checks the first 3 tests in your browser. Submit checks all 102 tests on the server, hidden ones included.