【力扣】767. 重构字符串

给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。

若可行，输出任意可行的结果。若不可行，返回空字符串。

示例 1:

输入: S = "aab"
输出: "aba"
示例 2:

输入: S = "aaab"
输出: ""
注意:

S 只包含小写字母并且长度在[1, 500]区间内。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reorganize-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

public String reorganizeString(String S) {
        if(S.length() < 2){
            return S;
        }
        //记录26个字母
        int []english = new int[26];
        int index = 0;
        int maxCount = 0; //得到最大个数的多少
        int maxCountIndex = 0; //得到哪个字母为个数最多的
        for(int i = 0; i< S.length(); i++){
            index = S.charAt(i) - 'a';
            english[index] = english[index]+1; 
            if (english[index] > maxCount) {
                maxCount = english[index];
                maxCountIndex = index;
            }
        }

        //如果某个字母的个数 大于 字符串的字符串的长度+1 / 2 ，说明无法将这个字符俩俩分割开
        if (maxCount > (S.length() + 1) >> 1) {
            return "";
        }

        //结果字符串数组
        char[] res = new char[S.length()];
        int resultIndex = 0;

        //将最多的字母从头开始放在偶数位
        while(english[maxCountIndex] > 0){
            res[resultIndex] = (char)(maxCountIndex + 'a');
            english[maxCountIndex]--;
            resultIndex+=2;
        }

        //按照每隔两个接着放字符
        for(int i =0; i < 26; i++){
            while(english[i] > 0){
                if (resultIndex >= res.length) {
                    //注意这里，如果已经超出了，则从1开始
                    resultIndex = 1;
                }
                res[resultIndex] = (char) (i + 'a');
                resultIndex += 2;
                english[i]--;
            }
        }
        return new String(res);
    }