CF196A.Lexicographically Maximum Subsequence

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

You've got string $s$ , consisting of only lowercase English letters. Find its lexicographically maximum subsequence.

We'll call a non-empty string s[p_{1}p_{2}...\ p_{k}]=s_{p1}s_{p2}...\ s_{pk}(1<=p_{1}<p_{2}<...<p_{k}<=|s|) a subsequence of string $s=s_{1}s_{2}...\ s_{|s|}$ .

String $x=x_{1}x_{2}...\ x_{|x|}$ is lexicographically larger than string $y=y_{1}y_{2}...\ y_{|y|}$ , if either |x|>|y| and $x_{1}=y_{1},x_{2}=y_{2},...\ ,x_{|y|}=y_{|y|}$ , or exists such number $r$ (r<|x|,r<|y|) , that $x_{1}=y_{1},x_{2}=y_{2},...\ ,x_{r}=y_{r}$ and x_{r+1}>y_{r+1} . Characters in lines are compared like their ASCII codes.

输入格式

The single line contains a non-empty string $s$ , consisting only of lowercase English letters. The string's length doesn't exceed $10^{5}$ .

输出格式

Print the lexicographically maximum subsequence of string $s$ .

输入输出样例

输入#1
```
ababba
```
输出#1
```
bbba
```
输入#2
```
abbcbccacbbcbaaba
```
输出#2
```
cccccbba
```

说明/提示

Let's look at samples and see what the sought subsequences look like (they are marked with uppercase bold letters).

The first sample: aBaBBA

The second sample: abbCbCCaCbbCBaaBA

首页