Chuỗi hạnh phúc dài nhất (Longest Happy String) trong C++

Cho số lượng tối đa a, b, c cho ký tự 'a','b','c'. Xây dựng chuỗi dài nhất không chứa "aaa", "bbb", "ccc" (không 3 ký tự giống nhau liên tiếp). Chỉ dùng 'a','b','c'.

Ví dụ

Đầu vào: a = 1, b = 1, c = 7
Đầu ra: "ccaccbcc" (hoặc "ccbccacc" - nhiều đáp án hợp lệ).

Thuật toán Tham lam + Priority Queue

1. Dùng max-heap (priority_queue) sắp theo số lượng còn lại.
2. Mỗi bước: lấy ký tự nhiều nhất (top).
3. Nếu 2 ký tự cuối kết quả = top → không thể dùng top (sẽ tạo 3 liên tiếp). Lấy ký tự thứ 2 (nếu có), dùng 1 lần, đẩy top trở lại heap.
4. Ngược lại: dùng min(2, count) lần top (ưu tiên dùng 2 để hết nhanh).
5. Cập nhật count, nếu > 0 đẩy lại heap. Lặp cho đến khi heap rỗng.

Triển khai C++

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

struct Node {
    char ch; int cnt;
    bool operator<(const Node& o) const { return cnt < o.cnt; }
};

class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        priority_queue pq;
        if (a) pq.push({'a', a});
        if (b) pq.push({'b', b});
        if (c) pq.push({'c', c});
        string res;
        while (!pq.empty()) {
            Node cur = pq.top(); pq.pop();
            int n = res.size();
            if (n >= 2 && res[n-1] == cur.ch && res[n-2] == cur.ch) {
                if (pq.empty()) break;
                Node nxt = pq.top(); pq.pop();
                res += nxt.ch;
                if (--nxt.cnt > 0) pq.push(nxt);
                pq.push(cur);
            } else {
                int use = min(2, cur.cnt);
                res += string(use, cur.ch);
                if ((cur.cnt -= use) > 0) pq.push(cur);
            }
        }
        return res;
    }
};

Độ phức tạp

• Thời gian: O((a+b+c) log 3) ≈ O(N) - heap kích thước tối đa 3.
• Không gian: O(1).

Kết quả kiểm thử

Đầu vào: 1,1,7
Đầu ra: ccbccacc (độ dài 8, hợp lệ)