Sắp xếp lại chuỗi so cho 2 ký tự liền kề không trùng nhau bằng C++

Cho chuỗi str, sắp xếp lại các ký tự sao cho không có 2 ký tự giống nhau nào liền kề. Nếu không thể, trả về chuỗi rỗng hoặc thông báo.

Ví dụ

Input: "itinn" → Output: "initn"
Input: "abbaabbaa" → Output: "ababababa"

Thuật toán Tham lam (Greedy) với Priority Queue / Counting Sort

Đếm tần suất mỗi ký tự. Luôn chọn ký tự còn lại nhiều nhất (và khác ký tự vừa đặt). Cách triển khai đơn giản:

Đếm tần suất 26 chữ cái.
Tìm ký tự có tần suất max (maxChar). Nếu freq[maxChar] > (n+1)/2 → không thể sắp xếp.
Đặt maxChar vào các vị trí chẵn (0, 2, 4...).
Điền các ký tự còn lại vào vị trí lẻ và vị trí chẵn còn trống.

Mã nguồn C++

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

char maxChar(const vector<int> &freq) {
    int maxFreq = 0; char ch = 'a';
    for (int i = 0; i < 26; i++)
        if (freq[i] > maxFreq) { maxFreq = freq[i]; ch = 'a' + i; }
    return ch;
}

string rearrangeString(string str) {
    int n = str.length();
    if (n == 0) return "";
    vector<int> freq(26, 0);
    for (char c : str) freq[c - 'a']++;

    char ch = maxChar(freq);
    int maxFreq = freq[ch - 'a'];
    if (maxFreq > (n + 1) / 2) return ""; // không thể

    string result(n, ' ');
    int idx = 0;
    // Đặt ký tự nhiều nhất vào vị trí chẵn
    while (maxFreq--) {
        result[idx] = ch;
        idx += 2;
    }
    freq[ch - 'a'] = 0;

    // Điền các ký tự còn lại
    for (int i = 0; i < 26; i++) {
        while (freq[i] > 0) {
            if (idx >= n) idx = 1; // chuyển sang vị trí lẻ
            result[idx] = 'a' + i;
            idx += 2;
            freq[i]--;
        }
    }
    return result;
}

int main() {
    string str = "itinn";
    string ans = rearrangeString(str);
    if (ans.empty())
        cout << "Không thể sắp xếp";
    else
        cout << "Kết quả: " << ans;
    return 0;
}

Kết quả

Kết quả: initn

Giải thích