Разбор задачи «Можно ли переставить в палиндром»

1. Идея

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

Главное свойство палиндрома такое:

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

Поэтому задача сводится к подсчёту количества букв, у которых нечётная частота.

• если таких букв не больше одной, ответ YES;
• иначе ответ NO.

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

Наблюдение 1

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

Например:

• abba — a и b встречаются по 2 раза;
• abcba — a и b встречаются по 2 раза, c встречается 1 раз и стоит в центре.

Наблюдение 2

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

Пример: строка ab.

• a встречается 1 раз;
• b встречается 1 раз.

Нечётных частот две, а центр в палиндроме только один. Значит, ответ NO.

Наблюдение 3

Так как строка состоит только из строчных латинских букв, достаточно массива из 26 элементов, где cnt[i] — количество вхождений буквы с номером i.

3. Алгоритм

1. Считать строку s.
2. Создать массив cnt из 26 нулей.
3. Для каждого символа строки увеличить счётчик соответствующей буквы.
4. Посчитать, сколько значений в cnt нечётные.
5. Если число нечётных частот <= 1, вывести YES, иначе вывести NO.

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

Докажем, что критерий odd <= 1 является правильным.

Если палиндром можно составить, то odd <= 1

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

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

Следовательно, количество нечётных частот не может быть больше 1.

Если odd <= 1, то палиндром можно составить

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

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

Значит, в обоих случаях палиндром существует.

Итак, условие odd <= 1 не только необходимо, но и достаточно.

5. Сложность

Подсчёт частот занимает O(n), где n — длина строки.

Проверка 26 букв занимает O(1).

Итоговая сложность:

• время: O(n)
• память: O(1), так как используется массив фиксированного размера 26

6. Код на C++17

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

using namespace std;

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

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

    int odd = 0;
    for (int x : cnt) {
        if (x % 2 != 0) {
            odd++;
        }
    }

    if (odd <= 1) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}

7. Код на Python 3

s = input().strip()

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

odd = 0
for x in cnt:
    if x % 2 != 0:
        odd += 1

if odd <= 1:
    print("YES")
else:
    print("NO")