Reorganize String ใน C++: จัดเรียงสตริงไม่ให้ตัวอักษรติดกันซ้ำ

โจทย์

กำหนดสตริง S จัดเรียงใหม่ไม่ให้ตัวอักษรติดกันเหมือนกัน ถ้าไม่ได้คืน empty string

ตัวอย่าง: "AAB" → "ABA"

แนวคิด: Greedy + Max Heap (Priority Queue)

นับความถี่ตัวอักษร ใส่ max-heap เรียงตามความถี่มาก→น้อย
แต่ละรอบดึง 2 ตัวบนสุด (ที่เหลือมากที่สุด) ใส่สลับกัน ลดความถี่ push กลับ

ขั้นตอน

1. นับความถี่ freq[c]
2. สร้าง priority_queue<pair<int,char>> pq (max-heap by count)
3. ans = ""
4. while !pq.empty():
   • ดึง one = pq.top(); pq.pop()
   • ถ้า pq.empty():
     • ถ้า one.first > 1 → return "" (ไม่ได้)
     • ans += one.second; return ans
   • ดึง two = pq.top(); pq.pop()
   • ans += one.second; ans += two.second
   • one.first--; two.first--
   • ถ้า one.first > 0 → pq.push(one)
   • ถ้า two.first > 0 → pq.push(two)
5. คืน ans

ตัวอย่างโค้ด 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"); // ABA
    return 0;
}

อินพุต / เอาต์พุต

Input: S = "AAB"

Output: ABA

ความซับซ้อน

• Time: O(n log α) - α = จำนวนตัวอักษรที่แตกต่างกัน (≤ 26 หรือ 52)
• Space: O(α)

เงื่อนไขเป็นไปได้

ต้องมี max_freq ≤ (n+1)/2 มิฉะนั้นจัดไม่ได้