1. Идея

Нужно переставить буквы строки так, чтобы получился палиндром.

Главное свойство палиндрома: символы слева и справа должны стоять попарно. Поэтому почти все буквы должны встречаться чётное число раз. Только одна буква может встретиться нечётное число раз — она может стоять в центре палиндрома.

Значит, задача сводится к двум шагам:

• посчитать, сколько раз встречается каждая буква;
• проверить, можно ли из этих количеств собрать палиндром.

Если нечётных букв больше одной, ответ невозможен. Иначе палиндром можно построить явно.

2. Наблюдения

Наблюдение 1

Если длина строки чётная, то все частоты букв должны быть чётными.

Пример:

• aabb → можно собрать abba
• aabc → нельзя, потому что есть две нечётные частоты: a:2, b:1, c:1

Наблюдение 2

Если длина строки нечётная, то ровно одна буква может иметь нечётную частоту.

Пример:

• aaabb → можно собрать ababa
• abc → нельзя, потому что нечётных букв три

Наблюдение 3

Если палиндром существует, его удобно строить так:

• в левую половину добавить по cnt[i] // 2 букв каждого вида;
• в середину поставить одну букву с нечётной частотой, если она есть;
• правую половину сделать как перевёрнутую левую.

Например, для строки aaabbbb:

• a:3, b:4
• левая половина: a и bb, то есть abb
• середина: a
• правая половина: bba
• ответ: abbabba

3. Алгоритм

1. Считать строку s.
2. Завести массив cnt из 26 элементов и посчитать частоты всех букв.
3. Пройти по всем буквам и посчитать, сколько частот нечётные.
   • одновременно запомнить букву с нечётной частотой, если она есть;
4. Если нечётных букв больше одной, вывести -1.
5. Иначе:
   • построить строку left, добавляя для каждой буквы cnt[i] // 2 копий;
   • построить middle:
     • пустая строка, если нечётной буквы нет;
     • одна буква, если нечётная буква есть;
   • построить right как перевёрнутую left;
   • вывести left + middle + right.

4. Почему это работает

Докажем корректность.

Когда ответ невозможен

В палиндроме все символы, кроме, возможно, одного центрального, обязаны разбиваться на пары: один символ слева, второй такой же справа.

Поэтому:

• каждая буква должна использоваться по две, четыре, шесть и так далее раз;
• только одна буква может остаться без пары и встать в центр.

Если букв с нечётной частотой больше одной, для всех них не хватит одного центрального места. Значит, палиндром составить нельзя.

Когда ответ возможен

Пусть нечётных частот не больше одной.

Тогда для каждой буквы можно взять cnt[i] // 2 штук в левую половину. Столько же автоматически пойдёт в правую половину. Все эти буквы будут стоять симметрично.

Если есть одна нечётная частота, то после разбиения по половинам останется ровно одна лишняя буква этого вида. Её и ставим в середину.

Полученная строка:

• использует все буквы;
• симметрична относительно центра;
• значит, является палиндромом.

Следовательно, алгоритм всегда:

• правильно выводит -1, если решения нет;
• строит корректный палиндром, если решение есть.

5. Сложность

Пусть n — длина строки.

• Подсчёт частот: O(n)
• Проверка нечётных частот: O(26)
• Построение ответа: O(n)

Итоговая сложность: O(n)

Память:

• массив частот из 26 чисел;
• строки ответа длины n

Итого: O(n)

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    string s;
    cin >> s;

    vector<int> cnt(26, 0);
    for (char c : s) {
        cnt[c - 'a']++;
    }

    int oddCount = 0;
    int oddChar = -1;
    for (int i = 0; i < 26; i++) {
        if (cnt[i] % 2 == 1) {
            oddCount++;
            oddChar = i;
        }
    }

    if (oddCount > 1) {
        cout << -1 << '\n';
        return 0;
    }

    string left = "";
    for (int i = 0; i < 26; i++) {
        left += string(cnt[i] / 2, char('a' + i));
    }

    string right = left;
    reverse(right.begin(), right.end());

    string middle = "";
    if (oddChar != -1) {
        middle = string(cnt[oddChar] % 2, char('a' + oddChar));
    }

    cout << left << middle << right << '\n';
    return 0;
}

7. Код на Python 3

s = input().strip()

cnt = [0] * 26
for c in s:
    cnt[ord(c) - ord('a')] += 1

odd_count = 0
odd_char = -1
for i in range(26):
    if cnt[i] % 2 == 1:
        odd_count += 1
        odd_char = i

if odd_count > 1:
    print(-1)
else:
    left_parts = []
    for i in range(26):
        left_parts.append(chr(ord('a') + i) * (cnt[i] // 2))

    left = "".join(left_parts)
    middle = ""
    if odd_char != -1:
        middle = chr(ord('a') + odd_char)

    right = left[::-1]
    print(left + middle + right)