← 返回题目列表

AtCoder · arc081_c

E. 不要成为子序列

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

字符串的子序列 S 是一个字符串,可以通过删除零个或多个字符来获得 S 不改变剩余字符的顺序。 例如, arc, artistic 和(空字符串)都是以下的子序列 artistic; abc 和 ci 不是。

给你一个字符串 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