767 reorganize string

https://leetcode.com/problems/reorganize-string/

class Solution {
    public String reorganizeString(String S) {
        int[] counts = new int[26];
        char[] input = S.toCharArray();
        for (char ch : input) {
            counts[ch - 'a']++;
        }
        char maxCh = 'a';
        int maxCnt = 0;
        for (int i = 0; i < counts.length; i++) {
            if (maxCnt < counts[i]) {
                maxCnt = counts[i];
                maxCh = (char)('a' + i);
            }
        }
        // 只有这种情况是不可能有解的，最多的元素没有足够的空间间隔排列
        if (maxCnt * 2 > input.length + 1) {
            return "";
        }
        int idx = 0;
        char[] output = new char[input.length];
        while (maxCnt > 0) {
            maxCnt--;
            output[idx] = maxCh;
            idx += 2;
        }
        for (int i = 0; i < counts.length; i++) {
            int count = counts[i];
            if (count == 0 || i == (maxCh - 'a')) {
                continue;
            }
            while (count > 0) {
                // wrap around, 置为1，只有第二多的元素可能wrap around
                if (idx >= output.length) {
                    idx = 1;
                }
                count--;
                output[idx] = (char)('a' + i);
                idx += 2;
            }
        }
        return new String(output);
    }
}

我觉得很奇怪的一道题，算法也没啥普适性，大概就是找出频率最大的间隔排列，剩下的元素填缝，注意任意元素填缝都是间隔填缝的，注意代码里idx wrap around的方式以及什么时候无解

"aaaabbccd"是一个理解这个算法的好例子