题目

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

题解

分桶策略，和两个月之前做的 621.Task Scheduler 类似。

两个月之前看的答案还有印象，如果是三个月之前，就说不准了。。

class Solution {
    public String reorganizeString(String s) {
        int L = s.length();
        int[][] count = new int[26][2];
        for (int i = 0; i < 26; i++) {
            count[i][1] = i;
        }
        for (int i = 0; i < L; i++) {
            count[s.charAt(i) - 'a'][0]++;
        }
        Arrays.sort(count, (o1, o2) -> o2[0] - o1[0]);
        
        // 贪心地按行平铺到桶内。桶的宽度，是出现最多的字母的出现次数
        int N = count[0][0];
        int[][] bucket = new int[L / N + 1][N];
        for (int[] r : bucket) {
            Arrays.fill(r, -1);
        }
        int total = 0;
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < count[i][0]; j++) {
                bucket[total / N][total % N] = count[i][1];
                total++;
            }
        }
        
        // 26路归并
        StringBuilder res = new StringBuilder();
        for (int j = 0; j < N; j++) {
            for (int i = 0; i < bucket.length; i++) {
                if (bucket[i][j] >= 0) {
                    res.append((char) ('a' + bucket[i][j]));
                }
            }
        }
        if (res.charAt(L - 1) == res.charAt(L - 2)) return "";
        return res.toString();
    }
}