[ARC081C] Don't Be a Subsequence

题意翻译

输入一个字符串a,求不是它的子序列的最短串。如果有多个,输出字典序最小的。

题目描述

[problemUrl]: https://arc081.contest.atcoder.jp/tasks/arc081_c 文字列 $ S $ に対して,その文字列を構成する文字を $ 0 $ 文字以上取り除き,残った文字を元の順番で並べて得られる文字列を $ S $ の部分列と呼びます. たとえば,`arc` や `artistic` や (空文字列) は `artistic` の部分列ですが,`abc` や `ci` は `artistic` の部分列ではありません. 英小文字からなる文字列 $ A $ が与えられます. このとき,英小文字からなる文字列で, $ A $ の部分列ではないようなもののうち,最も短いものを求めてください. ただし,そのようなものが複数ある場合には,辞書順で最小のものを求めてください.

输入输出格式

输入格式


Input is given from Standard Input in the following format: ``` $ A $ ```

输出格式


Print the lexicographically smallest string among the shortest strings consisting of lowercase English letters that are not subsequences of $ A $ .

输入输出样例

输入样例 #1

atcoderregularcontest

输出样例 #1

b

输入样例 #2

abcdefghijklmnopqrstuvwxyz

输出样例 #2

aa

输入样例 #3

frqnvhydscshfcgdemurlfrutcpzhopfotpifgepnqjxupnskapziurswqazdwnwbgdhyktfyhqqxpoidfhjdakoxraiedxskywuepzfniuyskxiyjpjlxuqnfgmnjcvtlpnclfkpervxmdbvrbrdn

输出样例 #3

aca

输入样例 #4

atcoderregularcontest

输出样例 #4

b

输入样例 #5

abcdefghijklmnopqrstuvwxyz

输出样例 #5

aa

输入样例 #6

frqnvhydscshfcgdemurlfrutcpzhopfotpifgepnqjxupnskapziurswqazdwnwbgdhyktfyhqqxpoidfhjdakoxraiedxskywuepzfniuyskxiyjpjlxuqnfgmnjcvtlpnclfkpervxmdbvrbrdn

输出样例 #6

aca

说明

### 制約 - $ 1\ \leq\ |A|\ \leq\ 2\ \times\ 10^5 $ - $ A $ は英小文字のみからなる. ### 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. ### Sample Explanation 1 `atcoderregularcontest` という文字列は `a` を部分列として含みますが,`b` は含みません. ### Sample Explanation 4 The string `atcoderregularcontest` contains `a` as a subsequence, but not `b`.