Codeforces Round 124 (Div. 1) |
---|
Закончено |
Дана строка 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.
ababba
bbba
abbcbccacbbcbaaba
cccccbba
Рассмотрим примеры и покажем, как именно выглядят искомые подпоследовательности (они выделены прописными буквами полужирным шрифтом).
Первый пример: aBaBBA
Второй пример: abbCbCCaCbbCBaaBA
Название |
---|