196A.md (1489B)
1 Source: https://codeforces.com/problemset/problem/196/A 2 3 A. Lexicographically Maximum Subsequence 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 You've got string *s*, consisting of only lowercase English letters. Find its lexicographically maximum subsequence. 22 23 We'll call a non-empty string *s*[*p*1*p*2... *p**k*] = *s**p*1*s**p*2... *s**p**k*(1 ≤ *p*1 < *p*2 < ... < *p**k* ≤ |*s*|) a subsequence of string *s* = *s*1*s*2... *s*|*s*|. 24 25 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. 26 27 Input 28 29 The single line contains a non-empty string *s*, consisting only of lowercase English letters. The string's length doesn't exceed 105. 30 31 Output 32 33 Print the lexicographically maximum subsequence of string *s*. 34 35 Examples 36 37 Input 38 39 ``` 40 ababba 41 ``` 42 43 Output 44 45 ``` 46 bbba 47 ``` 48 49 Input 50 51 ``` 52 abbcbccacbbcbaaba 53 ``` 54 55 Output 56 57 ``` 58 cccccbba 59 ``` 60 61 Note 62 63 Let's look at samples and see what the sought subsequences look like (they are marked with uppercase bold letters). 64 65 The first sample: aBaBBA 66 67 The second sample: abbCbCCaCbbCBaaBA