Автор разбора – В.М.Гуровиц
Подсчитаем, сколько раз во входном файле встречается каждая буква. Для этого можно воспользоваться массивом с индексами от A до Z.
Если в палиндроме общее количество символов четно, то для каждого символа найдется симметричный ему, поэтому каждая буква должна встречаться четное количество раз. Если же общее количество символов нечетно, то для каждого символа, кроме стоящего в центре палиндрома, найдется пара, поэтому все буквы кроме одной, должны встречаться четное число раз. Таким образом, если некоторая буква встречается во входном файле четное число раз, то мы можем использовать все ее вхождения, а из букв, которые встречаются нечетное число раз лишь одну (первую по алфавиту) мы сможем использовать нечетное число раз. Определим, какая буква встречается нечетное количество раз первой и сохраним ее в переменой first.
Если во входном файле нет букв, встречающихся нечетное число раз, то первый по алфавиту палиндром устроен следующим образом: сначала идет половина букв A, затем половина букв B, …, затем половина букв Z, далее вторая половина букв Z, вторая половина букв Y, …, вторая половина букв A.
Если во входном файле есть буквы, встречающиеся нечетное число раз, то первый по алфавиту палиндром устроен так же, как и палиндром четной длины, за одним исключением: в центре палиндрома расположена буква, записанная в переменную first.
Палиндром - это строка, которая читается одинаково как справа налево, так и слева направо.
На вход программы поступает набор больших латинских букв (не обязательно различных). Разрешается переставлять буквы, а также удалять некоторые буквы. Требуется из данных букв по указанным правилам составить палиндром наибольшей длины, а если таких палиндромов несколько, то выбрать первый из них в алфавитном порядке.
Выходные данные
В единственной строке выходных данных выдайте искомый палиндром.
Группы тестов
25 баллов —
(1 ≤
N
≤ 10)
.
25 баллов —
(1 ≤
N
≤
1 000
)
.
50 баллов — полные ограничения.
Примечание
Сложность работы программы должна быть O(n). Использование встроенной сортировки(sort, sorted), алгоритмов сортировки пузырёк/quick sort/merge sort и других запрещено!