/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 600 点
問題文
文字列 S に対して，その文字列を構成する文字を 0 文字以上取り除き，残った文字を元の順番で並べて得られる文字列を S の部分列と呼びます．
たとえば，arc や artistic や (空文字列) は artistic の部分列ですが，abc や ci は artistic の部分列ではありません．
英小文字からなる文字列 A が与えられます． このとき，英小文字からなる文字列で，A の部分列ではないようなもののうち，最も短いものを求めてください． ただし，そのようなものが複数ある場合には，辞書順で最小のものを求めてください．
制約
- 1 \leq |A| \leq 2 \times 10^5
- A は英小文字のみからなる．
入力
入力は以下の形式で標準入力から与えられる。
A
出力
英小文字からなる A の部分列でないような最短の文字列のうち，辞書順最小のものを出力せよ．
入力例 1
atcoderregularcontest
出力例 1
b
atcoderregularcontest という文字列は a を部分列として含みますが，b は含みません．
入力例 2
abcdefghijklmnopqrstuvwxyz
出力例 2
aa
入力例 3
frqnvhydscshfcgdemurlfrutcpzhopfotpifgepnqjxupnskapziurswqazdwnwbgdhyktfyhqqxpoidfhjdakoxraiedxskywuepzfniuyskxiyjpjlxuqnfgmnjcvtlpnclfkpervxmdbvrbrdn
出力例 3
aca
Score : 600 points
Problem Statement
A subsequence of a string S is a string that can be obtained by deleting zero or more characters from S without changing the order of the remaining characters.
For example, arc, artistic and (an empty string) are all subsequences of artistic; abc and ci are not.
You are given a string A consisting of lowercase English letters. Find the shortest string among the strings consisting of lowercase English letters that are not subsequences of A. If there are more than one such string, find the lexicographically smallest one among them.
Constraints
- 1 \leq |A| \leq 2 \times 10^5
- A consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
A
Output
Print the lexicographically smallest string among the shortest strings consisting of lowercase English letters that are not subsequences of A.
Sample Input 1
atcoderregularcontest
Sample Output 1
b
The string atcoderregularcontest contains a as a subsequence, but not b.
Sample Input 2
abcdefghijklmnopqrstuvwxyz
Sample Output 2
aa
Sample Input 3
frqnvhydscshfcgdemurlfrutcpzhopfotpifgepnqjxupnskapziurswqazdwnwbgdhyktfyhqqxpoidfhjdakoxraiedxskywuepzfniuyskxiyjpjlxuqnfgmnjcvtlpnclfkpervxmdbvrbrdn
Sample Output 3
aca