Задача B. Разнообразные строки

Автор:Рекомендации   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Будем называть разнообразностью строки количество символов, которые встречаются в ней ровно один раз. Например, разнообразность строки "INFORMATICS" - 9, поскольку символы "A", "C", "F", "M", "N", "O", "R", "S" и "T" встречаются в ней ровно один раз.

Для заданной строки S найдите подстроку, которая имеет наибольшую разнообразность. Если таких подстрок несколько, то найдите ту, которая минимальна в лексикографическом порядке.

Строка A меньше строки B в лексикографическом порядке, если выполняется одно из условий:

  1. A является началом B;
  2. для некоторого числа i первые i символов строки A совпадают с первыми i символами строки B, а i + 1-й символ в строке A идет в алфавите раньше i + 1-го символа в строке B.
Например, строка "SOL" меньше в лексикографическом порядке строк "SOLVE", "START", "TIME".

Формат входного файла

Входной файл содержит строку, состоящую из заглавных букв латинского алфавита.

Формат выходного файла

Выведите в выходной файл подстроку исходной строки, имеющую максимальную разнообразность среди всех ее подстрок. Если таких подстрок несколько, выведите минимальную в лексикографическом порядке.

Ограничения

Длина строки не превышает 2000 символов.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
ABBAC
BAC
2
OLYMP
OLYMP
3
AAA
A

0.077s 0.012s 15