Tái tổ chức chuỗi trong C++

Cho chuỗi S, sắp xếp lại các ký tự sao cho không có 2 ký tự giống nhau liền kề. Trả về chuỗi hợp lệ bất kỳ hoặc chuỗi rỗng nếu không thể.

Ví dụ: "AAB" → "ABA".

Thuật toán giải quyết (Heap ưu tiên theo tần suất)

1. Đếm tần suất ký tự, đẩy vào max-heap (priority_queue) theo tần suất.
2. Lặp khi heap chưa rỗng:
   • Lấy 2 phần tử tần suất cao nhất one, two.
   • Thêm ký tự của chúng vào kết quả.
   • Giảm tần suất, nếu còn > 0 → đẩy lại heap.
3. Nếu heap còn 1 phần tử với tần suất > 1 → không thể sắp xếp → trả về rỗng.

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string reorganizeString(string S) {
        unordered_map<char, int> freq;
        for (char c : S) freq[c]++;
        priority_queue<pair<int, char>> pq;
        for (auto &p : freq) pq.push({p.second, p.first});
        string ans;
        while (!pq.empty()) {
            auto one = pq.top(); pq.pop();
            if (pq.empty()) {
                if (one.first > 1) return "";
                ans += one.second;
                return ans;
            }
            auto two = pq.top(); pq.pop();
            ans += one.second;
            ans += two.second;
            if (--one.first > 0) pq.push(one);
            if (--two.first > 0) pq.push(two);
        }
        return ans;
    }
};

int main() {
    Solution ob;
    cout << ob.reorganizeString("AAB");
}

Đầu vào

S = "AAB"

Đầu ra

ABA