Smallest Subsequence of Distinct Characters

You are given a string \(S\) consisting of lowercase English alphabets. Your task is to find the smallest subsequence of \(S\) such that each character appears exactly once in the subsequence, and the subsequence is the smallest in lexicographical order among all possible answers.

Formally, let \(T\) be a subsequence of \(S\) that contains every unique character from \(S\) exactly once. Then \(T\) is chosen such that for any other valid subsequence \(T'\), we have \(T \leq T'\) in lexicographical order. The lexicographical comparison is defined in the usual way.

Hint: Consider using a greedy algorithm with a stack. Specifically, when deciding whether to include a character \(c\) in the subsequence, check and potentially remove the last character \(d\) in your current subsequence if \(c < d\) and \(d\) appears later in the string. In mathematical terms, while the stack is non-empty and the conditions \[ \text{stack}[-1] > c \quad \text{and} \quad i < \text{lastOccurrence}(\text{stack}[-1]) \] hold, pop the stack.

inputFormat

The input is read from stdin and consists of a single line containing the string \(S\) (1 \(\leq\) |\(S\)| \(\leq 10^5\)), where \(S\) is composed of only lowercase English letters.

outputFormat

Output to stdout a single line which is the smallest subsequence of \(S\) that contains every distinct character exactly once.

bcabc

abc