200812: [AtCoder]ARC081 E - Don't Be a Subsequence

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

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

加入题单

上一题 下一题 算法标签: