力扣 767 重构字符串

题意：给定一个字符串，重构字符串，让相同的字符，不相邻

思路：利用奇偶性，具体见代码注释

思想：字符规律

复杂度：时间O（n)，空间O(n)

class Solution {
    public String reorganizeString(String S) {
        if(S == null)
            return S;
        int len = S.length();
        if(len == 0)
            return S;
        
        char[] arr = new char[len];
        int[] count = new int[256];
        int max = 0;
        int index = -1;
        // 遍历字符串，找出字符串中每一个字符的个数，以及出现最多的字符
        for(int i=0;i<len;i++) {
            int temp = (int)S.charAt(i);
            count[temp]++;
            if(count[temp] > max) {
                max = count[temp];
                index = temp;
            }
        }
        
        // 如果最多的字符超过了一般，返回空
        if(max > (len +1)/2)
            return "";
        
        int cnt = 0;
        
        // 把最多的字符隔一位放入结果
        while(count[index] > 0) {
            arr[cnt] = (char)index;
            cnt = cnt+2;
            count[index]--;
        }
        
        // 遍历count把每一个不为0的字符，隔一位加入结果
        for(int i=0;i<256;i++) {
            while(count[i] > 0) {
                // 当奇数位用完之后，从头开始用偶数位放元素
                if(cnt >= len) 
                    cnt = 1;
                arr[cnt] = (char)i;
                cnt = cnt+2;
                count[i]--;
            }
        }
        
        return new String(arr);
    }
}