767

class Solution {
public:
    string reorganizeString(string s) {
        int freq[26]={0};
        for(char ch: s)
            freq[ch-'a']++;

        priority_queue<pair<int, int>> pq;
        for(int i=0; i<26; i++)
            if(freq[i])
                pq.push({freq[i], i});

        string ans = "";
        while(pq.size() > 1){
            auto num1 = pq.top(); pq.pop();
            auto num2 = pq.top(); pq.pop();
            num1.first--; num2.first--;
            if(num1.first)  pq.push(num1);
            if(num2.first)  pq.push(num2);
            ans += 'a'+num1.second;
            ans += 'a'+num2.second;
        }

        if(!pq.size() || (pq.size() == 1 && pq.top().first == 1)){
            if(pq.size())
                ans += (pq.top().second + 'a');
            return ans;
        }
        return "";
    }
};

-------------------------------

class Solution {
public:
    string reorganizeString(string S) {
        vector<int> cnt(26);
        int mostFreq = 0, i = 0;

        for(char c : S)
            if(++cnt[c - 'a'] > cnt[mostFreq])
                mostFreq = (c - 'a');

        if(2 * cnt[mostFreq] - 1 > S.size()) return "";

        while(cnt[mostFreq]) {
            S[i] = ('a' + mostFreq);
            i += 2;
            cnt[mostFreq]--;
        }

        for(int j = 0; j < 26; j++) {
            while(cnt[j]) {
                if(i >= S.size()) i = 1;
                S[i] = ('a' + j);
                cnt[j]--;
                i += 2;
            }
        }

        return S;
    }
};