class Solution {
public:
    string reorganizeString(string s) {
        int count[26] = {};
        int max_count = 0;
        char max_char = 0;
        for (char c : s) {
            count[c - 'a']++;
            if (count[c - 'a'] > max_count) {
                max_count = count[c - 'a'];
                max_char = c;
            }
        }
        if (max_count > ceil((double)s.size() / 2)) {
            return "";
        }
        int k = 0;
        char ca[s.size() + 1] = {};
        for (int j = 0; j < count[max_char - 'a']; ++j) {
            ca[k] = max_char;
            k += 2;
        }
        if (k >= s.size()) {
            k = 1;
        }
        for (int i = 0; i < 26; ++i) {
            if (i != max_char - 'a') {
                for (int j = 0; j < count[i]; ++j) {
                    ca[k] = 'a' + i;
                    k += 2;
                    if (k >= s.size()) {
                        k = 1;
                    }
                }
            }
        }
        ca[s.size()] = 0;
        string res(ca);
        return res;
    }
};