Sắp xếp lại chuỗi cách nhau ít nhất k khoảng trong C++

Cho chuỗi không rỗng s và số nguyên k. Sắp xếp lại chuỗi sao cho các ký tự giống nhau cách nhau ít nhất k khoảng. Nếu không thể, trả về chuỗi rỗng.

Ví dụ: s = "aabbcc", k = 3 → "abcabc" (các ký tự giống nhau cách nhau 3 vị trí).

Phương pháp giải

Sử dụng hàng đợi ưu tiên (max-heap) theo tần suất ký tự. Lấy ký tự xuất hiện nhiều nhất, thêm vào kết quả, giảm tần suất, đưa vào hàng đợi chờ (deque) kích thước k. Khi deque đầy, lấy phần tử đầu ra, nếu còn tần suất > 0 thì đưa trở lại heap.

Ví dụ chương trình

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

struct Comparator {
    bool operator()(pair a, pair b) {
        return !(a.second > b.second);
    }
};

class Solution {
public:
    string rearrangeString(string s, int k) {
        string ret = "";
        unordered_map m;
        for (char c : s) m[c]++;
        
        priority_queue, vector>, Comparator> pq;
        for (auto& p : m) pq.push(p);
        
        deque> dq;
        while (!pq.empty()) {
            auto curr = pq.top(); pq.pop();
            ret += curr.first;
            curr.second--;
            dq.push_back(curr);
            if (dq.size() >= k) {
                auto front = dq.front(); dq.pop_front();
                if (front.second > 0) pq.push(front);
            }
        }
        while (!dq.empty() && dq.front().second == 0) dq.pop_front();
        return dq.empty() ? ret : "";
    }
};

int main() {
    Solution ob;
    cout << ob.rearrangeString("aabbcc", 3);
    return 0;
}

Đầu vào

"aabbcc", 3

Đầu ra

bacbac