Description

Submission

class Solution {
    int cnt[26];
public:
    string reorganizeString(string s) {
        int len = s.length();
        string ret = s;

        for(char ch: s) {
            ++cnt[ch-'a'];
        }

        int maxn = 0;
        for(int i = 1; i < 26; ++i) {
            if(cnt[i] > cnt[maxn]) {
                maxn = i;
            }
        }

        if(cnt[maxn] * 2 > len + 1) return "";

        int ptr = maxn;
        for(int i = 0; i < len; i += 2) {
            while(!cnt[ptr]) ptr = (ptr + 1) % 26;
            ret[i] = ptr + 'a';
            --cnt[ptr];
        }

        for(int i = 1; i < len; i += 2) {
            while(!cnt[ptr]) ptr = (ptr + 1) % 26;
            ret[i] = ptr + 'a';
            --cnt[ptr];
        }

        return ret;
    }
};