Задачі
Изоморфизмы – 2
Изоморфизмы – 2
Две строки \textbf{s} и \textbf{t} называются \textit{изоморфными}, если можно так переобозначить все буквы первой строки, чтобы получить вторую. Конечно, разные буквы должны быть переобозначены разными буквами, а одинаковые --- одинаковыми.
Например, строки "\textbf{aba}" и "\textbf{сас}" изоморфные. Соответствующее переобозначение: обозначим букву '\textbf{a}' буквой '\textbf{c}', а букву '\textbf{b}' буквой '\textbf{a}'. А строки "\textbf{xy}" и "\textbf{xx}" не изоморфные.
Вам задана строка \textbf{s}. Введем функцию \textbf{f(t)} (\textbf{t} --- непустая строка), которая равна количеству подстрок строки \textbf{s}, изоморфных \textbf{t}, умножить на длину строки \textbf{t}. Ваша задача, найти строку \textbf{t}, состоящую из маленьких латинских букв, такую, что значение \textbf{f(t)} максимально возможное.
\InputFile
В первой строке записана строка \textbf{s} (\textbf{1} ≤ \textbf{|s|} ≤ \textbf{4000}), строка состоит из маленьких латинских букв.
\OutputFile
Выведите оптимальную строку \textbf{t}, если таких несколько, выведите любую. Выведенная строка должна состоять из маленьких латинских букв.
Вхідні дані #1
abacabadabacaba
Вихідні дані #1
abaca