← 返回题目列表

Codeforces · 196/A

A. 字典顺序最大子序列

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

你有字符串 s,仅包含小写英文字母。找到它的字典顺序最大子序列。

我们将非空字符串 s[p1p2... pk] = sp1sp2... spk(1 ≤ p1 < p2 < ... < pk ≤ |s|) 称为字符串 s = s1s2... s|s| 的子序列。

字符串 x = x1x2... x|x|按字典顺序大于字符串 y = y1y2... y|y|,如果 |x| > |y|且 x1 = y1, x2 = y2, ... , x|y| = y|y|,或存在这样的数字 r (r < |x|, r < |y|),即 x1 = y1,x2 = y2,...,xr = yr 和 xr + 1 > yr + 1。行中的字符像其 ASCII 代码一样进行比较。

输入

单行包含一个非空字符串 s,仅由小写英文字母组成。字符串的长度不超过105。

输出

打印字符串 s 的字典顺序最大子序列。

示例

输入 #1

ababba

输出 #1

bbba

输入 #2

abbcbccacbbcbaaba

输出 #2

cccccbba

注意

让我们看一下样本,看看所寻找的子序列是什么样的(它们用大写粗体字母标记)。

第一个样本:aBaBBA

第二个样本:abbCbCCaCbbCBaaBA