Lexicographically Maximum Subsequence

题意翻译

## 题目描述: 你现在有一个只包含小写英文字母的字符串,要求求它的最大字典序子序列。 我们把一个非空字符串s[p_{1}p_{2}...\ p_{k}]=s_{p1}s_{p2}...\ s_{pk}(1<=p_{1}<p_{2}<...<p_{k}<=|s|)叫做字符串s=s1s2…s|s|的一个子序列。 如果|x|>|y|而且x1=y1,x2=y2…X|y|=Y|y|或者存在一个数字r (r<|x|,r<|y|)满足x1=y1,x2=y2…X|y|=Y|y|并且x_{r+1}>y_{r+1},那么字符串x=x1x2…x|x|在字典序上比字符串y=y1y2…y|y|大。在行中的字符根据他们的ASCII码进行比较 ## 输入格式: 只有一行,包括一个非空的只含小写字母的字符串s,字符串长度不超过10^5 ## 输出格式: 输出只有一行,输出字符串s的 最大字典序子序列 ## 说明/提示: 让我们看一下样例并看一看待求的子序列长什么样子(用大写粗体字母标注) 样例1:a**B**a**BBA** 样例2:abb**C**b**CC**a**C**bb**CB**aa**BA**

题目描述

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}&lt;p_{2}&lt;...&lt;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|&gt;|y| $ and $ x_{1}=y_{1},x_{2}=y_{2},...\ ,x_{|y|}=y_{|y|} $ , or exists such number $ r $ $ (r&lt;|x|,r&lt;|y|) $ , that $ x_{1}=y_{1},x_{2}=y_{2},...\ ,x_{r}=y_{r} $ and $ x_{r+1}&gt;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