---

 

记录上一个写入的字母，找除了这个字母以外的出现次数最多的字母插入。

class Solution {
public:
    string reorganizeString(string S) {
        int alp[26];
        int i;
        for(i=0;i<26;i++){
            alp[i]=0;
        }
        for(i=0;i<S.length();i++){
            alp[S[i]-'a']++;
        }
        string ans="";
        int maxx,tmp=-1,maxpos;
        while(ans.length()<S.length()){
            maxx=0;
            maxpos=-1;
            for(i=0;i<26;i++){
                if(alp[i]>maxx&&i!=tmp){
                    maxx=alp[i];
                    maxpos=i;
                }
            }
            if(maxpos==-1) return "";
            ans+=(char)('a'+maxpos);
            alp[maxpos]--;
            tmp=maxpos;
        }
        return ans;
    }
};