สตริง Happy ยาวที่สุดใน C++

สตริงจะ "happy" ถ้าไม่มี substring 'aaa', 'bbb', 'ccc' กำหนด a,b,c เป็นจำนวนสูงสุดของ 'a','b','c' หา happy string ยาวที่สุด

ตัวอย่าง: a=1, b=1, c=7 → "ccaccbcc" (หรือ "ccbccacc")

วิธีแก้ปัญหา (Greedy + Priority Queue)

1. ใช้ max-heap เรียงตาม count ที่เหลือ
2. ทุกขั้นตอน:
   • ดึงตัวที่เหลือมากสุด
   • ถ้าตัวสุดท้ายของผลลัพธ์เหมือนตัวนี้ ให้ดึงตัวที่สองมากสุดแทน
   • ตัดสินใจเพิ่ม 1 หรือ 2 ตัว: ถ้า count ต่างจากตัวถัดไป < 2 ให้ใส่ 1 ตัว มิฉะนั้นใส่ 2 ตัว
   • อัปเดต count และ push กลับ heap
3. ทำซ้ำจน heap ว่าง

ตัวอย่างโค้ด C++

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

struct Data{ 
    char a; 
    int cnt; 
    int idx; 
    Data(char c, int x, int k){ a = c; cnt = x; idx = k; } 
}; 

struct Cmp{ 
    bool operator()(Data& a, Data& b) { 
        return !(a.cnt > b.cnt); 
    } 
}; 

class Solution { 
public: 
    string longestDiverseString(int a, int b, int c) { 
        priority_queue<Data, vector<Data>, Cmp> pq; 
        if (a) pq.push(Data('a', a, 0)); 
        if (b) pq.push(Data('b', b, 0)); 
        if (c) pq.push(Data('c', c, 0)); 
        
        int idx = 1; 
        string ret = ""; 
        while (true) { 
            Data temp = pq.top(); pq.pop(); 
            if (ret.size() && ret.back() == temp.a) { 
                if (pq.empty()) break; 
                Data x = temp; 
                temp = pq.top(); pq.pop(); 
                pq.push(x); 
            } 
            int val = 0; 
            if (!pq.empty() && temp.cnt - pq.top().cnt < 2) val = 1; 
            else val = min(temp.cnt, 2); 
            ret += string(val, temp.a); 
            temp.cnt -= val; 
            if (pq.empty()) break; 
            temp.idx = idx; 
            if (temp.cnt > 0) pq.push(temp); 
            idx++; 
        } 
        return ret; 
    } 
}; 

int main(){ 
    Solution ob; 
    cout << (ob.longestDiverseString(1,1,7)); 
}

ข้อมูลนำเข้า

1,1,7

ผลลัพธ์

ccbccacc