Определения
Условно назовем строку S уникальной, если все ее символы юникальны (нет повторений).
Строка S2 является производной от строки S1, если мы можем получить S2 удалив несколько символов из S1.
Строка S1 прекраснее чем S2, если S1 имеет большую длинну или одинаковая по длинне но больше по лексикографическому порядку.
Задание
Найти самую прекрасную уникальную строку, которая бы была производной от данной.
Input
Строка S длинной более чем 1 000 000 (10^6) символов, все символы – латиница в нижнем регистре.
Output
Вывести самую прекрасную уникальную строку, которая бы была производной от строки S.
Пример входных данных
babab
Что должна вернуть программа
ba
Объяснение
В данном примере уникальными являются “ab” и “ba“, но “ba” прекраснее “ab“.
Тест-кейсы
- input1: babab
- output1: ba
- input2: nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnqsknbarpabgokbsrfhmeklrle
- output2: tsocrpkijgdqnbafhmle