Задача: 267. Palindrome Permutation II
Сложность: medium

Пример:

Input: s = "aabb"
Output: ["abba","baab"]

👨‍💻 Алгоритм:

1⃣Подсчёт частоты символов
Создаем хеш-таблицу частот. Если количество символов с нечетной частотой больше 1 — палиндром невозможен.

2⃣Формирование первой половины
Из каждого символа берём его частоту пополам и формируем строку half. Символ с нечетной частотой (если есть) сохраняем как центральный.

3⃣Генерация палиндромов
С помощью backtracking создаём все уникальные перестановки строки half, дополняем их зеркально. Если есть центральный символ — добавляем его в середину.

😎 Решение:

class Solution {
private:
    void backtrack(string& half, vector<bool>& used, string& path, string& mid, vector<string>& res) {
        if (path.size() == half.size()) {
            string rev = path;
            reverse(rev.begin(), rev.end());
            res.push_back(path + mid + rev);
            return;
        }

        for (int i = 0; i < half.size(); ++i) {
            if (used[i]) continue;
            if (i > 0 && half[i] == half[i - 1] && !used[i - 1]) continue;

            used[i] = true;
            path.push_back(half[i]);
            backtrack(half, used, path, mid, res);
            path.pop_back();
            used[i] = false;
        }
    }

public:
    vector<string> generatePalindromes(string s) {
        unordered_map<char, int> freq;
        for (char c : s) freq[c]++;

        int oddCount = 0;
        string mid = "", half = "";
        for (auto& [ch, count] : freq) {
            if (count % 2 != 0) {
                oddCount++;
                mid = ch;
            }
            half += string(count / 2, ch);
        }

        if (oddCount > 1) return {};

        sort(half.begin(), half.end());
        vector<string> res;
        vector<bool> used(half.size(), false);
        string path;
        backtrack(half, used, path, mid, res);
        return res;
    }
};

Ставь 👍 и забирай 📚 Базу знаний