Задача №113934. Ох уж эти палиндромы
Назовём палиндромом непустую строку, которая читается одинаково справа налево и слева направо. Например, « abcba », « a » и « abba » являются палиндромами, а « abab » и « xy » не являются.
Назовём подстрокой строки строку, полученную отбрасыванием некоторого (возможно, нулевого) количества символов с начала и с конца строки. Например, « abc », « ab » и « c » являются подстроками строки « abc », а « ac » и « d » не являются.
Назовем палиндромностью строки количество её подстрок, которые являются палиндромами. Например, палиндромность строки « aaa » равна \(6\), так как все её подстроки являются палиндромами, а палиндромность строки « abc » равна \(3\), так как только подстроки длины \(1\) являются палиндромами.
Вам дана строка \(s\). Вы можете произвольным образом переставлять символы в ней. Требуется получить строку, имеющую максимальную палиндромность.
В первой строке задано целое число \(n\) (\(1 \le n \le 100\,000\)) — длина строки \(s\).
Во второй строке задана строка \(s\), состоящая из \(n\) строчных букв латинского алфавита.
Выведите строку \(t\), которая состоит из тех же символов (с учётом кратностей), что и \(s\), и имеет максимальную палиндромность среди всех строк, которые могут быть получены из \(s\) перестановкой символов.
Если подходящих строк несколько, выведите любую.
В первом примере у строки « ololo » есть \(9\) подстрок-палиндромов: « o », « l », « o », « l », « o », « olo », « lol », « olo », « ololo ». Обратите внимание, что некоторые подстроки совпадают, но учитываются несколько раз.
Во втором примере палиндромность строки « abccbaghghghgdfd » равна \(29\).
5 oolol
ololo
16 gagadbcgghhchbdf
abccbaghghghgdfd