Підпослідовність
Дано рядок . Вам потрібно знайти рядок мінімальної довжини, який не є підпослідовністю рядка . Якщо таких рядків кілька, то знайдіть лексикографічно мінімальний. Можна отримати половину балів, якщо ви виведете рядок мінімальної довжини.
Нагадаємо, що рядок є підпослідовністю рядка , якщо можна отримати з , видаливши кілька (можливо, жоден або всі) символів.
Рядок лексикографічно менший рядка тоді і тільки тоді, коли виконується один з двох пунктів:
— префікс , але ;
у першій позиції, де та відрізняються, у рядку знаходиться буква, яка зустрічається в алфавіті раніше, ніж відповідна буква у .
Вхідні дані
Перший рядок містить рядок ().
Вихідні дані
Виведіть рядок.
Приклади
Примітка
Зверніть увагу, що у рядку присутні усі можливі символи, а також рядок починається та завершується на «a
».
Оскільки присутні усі можливі символи, то відповідь не може бути . Оскільки після першої літери «a
» є всі інші літери, то зрозуміло, що перший символ відповіді буде як мінімум «b
». Є підрядок «ba
», але немає «bb
», тому відповідь — «bb
».
Якби цей тест оцінювався, то ви отримали б бали, якби вивели «bb
». А якби ви вивели будь-який інший рядок довжини (наприклад, «aa
», «ba
», «zz
»), то отримали б бал.
Оцінювання
У цій задачі буде тестів, кожен з яких оцінюється у бали. Якщо ви виведете правильну відповідь у тесті, то ви отримаєте бали за нього.
Якщо ж рядок, який ви вивели, матиме таку ж довжину, що й відповідь, то ви отримаєте бал за нього. Цей рядок повинен містити лише малі літери англійського алфавіту. Зверніть увагу, що більше ніяких вимог до цього рядка немає. Тобто, ви можете навіть вивести рядок, який є підпослідовністю . Головне, щоб довжина була такою ж, як і відповідь.