#767 Reorganize String

string reorganizeString(string s) {
    // 1. Подсчёт частот символов
    vector<int> freq(26, 0);
    for (char c : s) {
        freq[c - 'a']++;
    }

    // 2. Max-heap: храним пары (частота, символ)
    priority_queue<pair<int, char>> pq;
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) {
            pq.push({ freq[i], 'a' + i });
        }
    }

    // 3. Проверка на возможность перестановки
    // Если самый частый символ встречается больше (n+1)/2 раз — невозможно
    if (pq.top().first > (s.length() + 1) / 2) {
        return "";
    }

    // 4. Построение результата
    string result = "";

    while (pq.size() >= 2) {
        // Берём два самых частых символа
        auto first = pq.top(); pq.pop();
        auto second = pq.top(); pq.pop();

        // Добавляем их в результат
        result += first.second;
        result += second.second;

        // Уменьшаем частоты и возвращаем в heap, если остались
        if (--first.first > 0) pq.push(first);
        if (--second.first > 0) pq.push(second);
    }

    // 5. Если остался один символ (с частотой 1)
    if (!pq.empty()) {
        result += pq.top().second;
    }

    return result;
}