Краевая олимпиада 2006 II тур - Разнообразные строки

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

задачи
видимые пробелы
простые формулы
широкий текст
редактор

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

Условие

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

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

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

A является началом B;
для некоторого числа 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`