Remove Duplicate Letters

Given a string \( s \), remove the minimum number of characters so that the resulting string contains no duplicate letters and is lexicographically smallest. In other words, find a string \( r \) obtained from \( s \) that satisfies:

\( r \) contains every character at most once, and among all such strings, \( r \) is lexicographically smallest.

Examples:

• For input bcabc, the output is abc.
• For input cbacdcbc, the output is acdb.
• For input cbcbcd, the output is bcd.

You can prove that the answer is unique.

inputFormat

The input consists of a single line containing the string \( s \) (with \( 1 \leq |s| \leq 10^5 \)).

outputFormat

Output a single line: the lexicographically smallest string that can be obtained by removing duplicate letters from \( s \).

bcabc

abc