Smallest Lexicographic Subsequence

Sammy has a sequence of lowercase English letters given as a string s. He wants to find the lexicographically smallest subsequence of s that contains every distinct character present in s exactly once.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

In other words, if the set of distinct characters in s is denoted by \(D(s)\), you need to find a subsequence \(t\) of s such that:

• \(D(t) = D(s)\)
• \(t\) is the lexicographically smallest among all such possible subsequences.

Note: A string \(a\) is considered lexicographically smaller than a string \(b\) if at the first position where they differ, the character in \(a\) comes before the character in \(b\) in the alphabet.

Example: For s = "cbacdcbc", the answer is acdb because it is the smallest subsequence that contains all the distinct characters of s.

inputFormat

The input consists of a single line containing the string s consisting of lowercase English letters.

outputFormat

Output a single line containing the lexicographically smallest subsequence of s that contains every distinct character from s.

cbacdcbc

acdb