e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Ukrainian Junior & Girls' Olympiads in Informatics, Final

Підпослідовність

Дано рядок $s$. Вам потрібно знайти рядок мінімальної довжини, який не є підпослідовністю рядка $s$. Якщо таких рядків кілька, то знайдіть лексикографічно мінімальний. Можна отримати половину балів, якщо ви виведете рядок мінімальної довжини. Нагадаємо, що рядок $a$ є підпослідовністю рядка $b$, якщо можна отримати $a$ з $b$, видаливши кілька (можливо, жоден або всі) символів. Рядок $a$ лексикографічно менший рядка $b$ тоді і тільки тоді, коли виконується один з двох пунктів: \begin{itemize} \item $a$~--- префікс $b$, але $a \ne b$; \item у першій позиції, де $a$ та $b$ відрізняються, у рядку $a$ знаходиться буква, яка зустрічається в алфавіті раніше, ніж відповідна буква у $b$. \end{itemize} \InputFile Перший рядок містить рядок $s$ ($1 \leq |s| \leq 10^5$). \OutputFile Виведіть рядок. \Note Зверніть увагу, що у рядку присутні усі можливі символи, а також рядок починається та завершується на <<\t{a}>>. Оскільки присутні усі можливі символи, то відповідь не може бути $1$. Оскільки після першої літери <<\t{a}>> є всі інші літери, то зрозуміло, що перший символ відповіді буде як мінімум <<\t{b}>>. Є підрядок <<\t{ba}>>, але немає <<\t{bb}>>, тому відповідь~--- <<\t{bb}>>. Якби цей тест оцінювався, то ви отримали б $2$ бали, якби вивели <<\t{bb}>>. А якби ви вивели будь-який інший рядок довжини $2$ (наприклад, <<\t{aa}>>, <<\t{ba}>>, <<\t{zz}>>), то отримали б $1$ бал. \Scoring У цій задачі буде $50$ тестів, кожен з яких оцінюється у $2$ бали. Якщо ви виведете правильну відповідь у тесті, то ви отримаєте $2$ бали за нього. Якщо ж рядок, який ви вивели, матиме таку ж довжину, що й відповідь, то ви отримаєте $1$ бал за нього. Цей рядок повинен містити лише малі літери англійського алфавіту. Зверніть увагу, що більше ніяких вимог до цього рядка немає. Тобто, ви можете навіть вивести рядок, який є підпослідовністю $s$. Головне, щоб довжина була такою ж, як і відповідь.
Time limit 1 second
Memory limit 256 MiB
Input example #1
aqwertyuiopsdfghjklzxcvbnma
Output example #1
bb
Author Anton Tsypko