ArabellaCPC 2019 |
---|
Finished |
Ayoub has a string $$$S$$$ consists of only lower case Latin letters, and he wants you to make some operations on it:
Ayoub wants you to make the string lexicographically maximal using the mentioned operations as many times as you want, can you help him?
String $$$x = x_1x_2... x_{|x|}$$$ is lexicographically larger than string $$$y = y_1y_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 input contains a single string $$$S$$$ $$$(1 \leq |S| \leq 10^5)$$$.
It is guaranteed that string $$$S$$$ consists of only lower case Latin letters.
print the lexicographically maximal string that could be obtained using these two operations.
abbx
xca
zyayz
zzza
In the first test case Ayoub replaced $$$"bb"$$$ with $$$"c"$$$ so the string has been changed to $$$"acx"$$$, then he swapped 'a' with 'x' so the result is $$$"xca"$$$ and it is the lexicographically maximal string.
Name |
---|