Remove Duplicate Letters

MediumStringStackGreedyMonotonic Stack

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example 1:

Input: s = "bcabc"
Output: "abc"

Example 2:

Input: s = "cbacdcbc"
Output: "acdb"

Constraints:

1 <= s.length <= 104
s consists of lowercase English letters.

Examples

Example 1

Input: bcabc

Output: abc

Example 2

Input: cbacdcbc

Output: acdb

Input:

bcabc

Expected Output:

abc

Remove Duplicate Letters

Examples

Hint 1