767. 重构字符串

题目描述：

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

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

示例 1:

输入: S = "aab"
输出: "aba"

示例 2:

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

注意:

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

思路：

1、当某个字符出现的次数大于字符总数的一半时，必然无法进行重构，这时候返回空字符串。
2、将字符串中的字符按照26个字幕的排序放到数组中，字符出现的次数作为数组的元素。
3、遍历数组，将字符串中的字符依次存储到字符数组中。将字符个数小于字符串长度的一半的字符存入奇数下标位置（例如vvvlo中，l和o都需要存入奇数下标位置，v需要存入偶数下标位置），否则存入偶数下标位置(例如上面例子aab中，aa就需要存入偶数下标位置)。

Java解法：

class Solution {
    public String reorganizeString(String S) {
        int len = S.length();
        int[] counts = new int[26];
        int maxlen = 0;
        for (int i = 0 ; i < len; i++){
            if (++counts[S.charAt(i) - 'a'] > maxlen)
            {
                maxlen = counts[S.charAt(i) - 'a'];
            }
        }
        if (maxlen > (len+1)/2)
        {
            return "";
        }
        char[] str = new char[len];
        int even = 0, odd = 1;
        for(int i = 0 ; i < 26; i++)
        {
            while(counts[i] > 0 && counts[i] < (len/2+1) && odd<len )
            {
                str[odd] = (char)(i + 'a');
                counts[i]--;
                odd += 2;
            }
            while(counts[i] > 0)
            {
                str[even] = (char)(i + 'a');
                counts[i]--;
                even += 2;
            }
        }
        return new String(str);
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers