class Solution {
public:
    string reorganizeString(string S) {
        map<char, int> M;
        int max_val = 0;
        for (int i = 0; i < S.length(); i++) {
            M[S[i]]++;
            max_val = max(max_val, M[S[i]]);
        }

        vector<pair<char, int>> FreqOrder;
        for (const auto& k: M) {
            cout << k.first << ", " << k.second << endl;
            FreqOrder.push_back({k.first, k.second});
        }

        sort(FreqOrder.begin(), FreqOrder.end(), [](const pair<char, int>& A, const pair<char, int>& B) {
            return A.second > B.second;
        });

        if (max_val > (S.length() + 1)/2) return "";
        vector<char> result (S.length(), ' ');
        int index = 0;
        for (const auto& k: FreqOrder) {
            for (int i = 0; i < k.second; i++) {
                result[index] = k.first;
                if (index + 2 >= S.length()) index = 1;
                else index = (index + 2) ;
            }
        }
        string ret;
        for (int i = 0; i< result.size(); i++)
            ret += result[i];
        return ret;
    }
};