All problems

Remove Duplicate Letters

Medium · stack

You are given a string text made of lowercase English letters.

Delete some of its letters so that every distinct letter that appears in text is kept exactly once. The letters you keep stay in the same relative order they had in text.

Of all the strings you could end up with, return the one that comes first in dictionary order. Two strings are compared letter by letter from the left, and the first position where they differ decides: the string with the earlier letter of the alphabet wins.

Examples

Example 1

Input: text = "dbadcb"

Output: "adcb"

The letters a, b, c and d must each appear once. Keeping the first d or the first b would put a bigger letter first, so the result starts with a, then d, c and b in their original order.

Example 2

Input: text = "aaaa"

Output: "a"

Only the letter a exists, so one copy is kept.

Example 3

Input: text = "zyxzy"

Output: "xzy"

x appears only once, so it is kept; after it the only z and y that remain are in that order.

Constraints