358. K 距离间隔重排字符串

给你一个非空的字符串 s 和一个整数 k ，你要将这个字符串 s 中的字母进行重新排列，使得重排后的字符串中相同字母的位置间隔距离 至少 为 k 。如果无法做到，请返回一个空字符串 ""。

示例 1：

输入: s = "aabbcc", k = 3
输出: "abcabc" 
解释: 相同的字母在新的字符串中间隔至少 3 个单位距离。

示例 2:

输入: s = "aaabc", k = 3
输出: "" 
解释: 没有办法找到可能的重排结果。

示例 3:

输入: s = "aaadbbcc", k = 2
输出: "abacabcd"
解释: 相同的字母在新的字符串中间隔至少 2 个单位距离。

提示：

• 1 <= s.length <= 3 * 10^5
• s 仅由小写英文字母组成
• 0 <= k <= s.length

做题结果

成功，优先队列，滑动窗口都没用，就纯纯的排序+数组+集合（也可以不要，就纯数组也行）

方法：排序

1. 有长度为 n 的字符串，每k 个分为一组，可以分出 part=(n+k-1)组，那如果有字符数目超过part,一定无法构成模板串，直接返回

2. 字母用数组计数，记录每种字符的数量

3. 长度大于0的放入列表，按数量倒排

4. 每次取尽量数量多的 k 的字符，放入答案

5. 需要检查索引位置，如果和前面距离太近了，那就换同样数量的其他字母试试

6. 每次排一下顺序（只有长度26，所以一直排也没关系）

class Solution {
        public String rearrangeString(String s, int k) {
            if(k==0) return s;
            int[] arr = new int[26];
            int n = s.length();
            int part = (n+k-1)/k;//每部分最大几个
 
            for(int i = 0; i < n; i++){
                int index = s.charAt(i)-'a';
                arr[index]++;
                if(arr[index]>part){
                    return "";
                }
            }
 
            //按数量顺序倒序
            List<int[]> list = new ArrayList<>();
            for(int i = 0; i < 26; i++){
                if(arr[i]>0){
                    list.add(new int[]{i,arr[i]});//字母，数量
                }
            }
 
            //按数量倒排
            list.sort((a,b)->b[1]-a[1]);
 
            int[] lastId = new int[26];//上次的索引位
            Arrays.fill(lastId,-1);
            StringBuilder sb = new StringBuilder();
            boolean move = true;
            for(int i = 0; i < n&&move; ){
                move = false;
                //从数量多分配到数量少的
                for (int[] data : list) {
                    //没得分跳出
                    if (data[1] == 0) break;
 
                    int id = sb.length();
                    //距离不够远，跳过
                    if(lastId[data[0]]!=-1 && id-lastId[data[0]]<k)
                        continue;
                    //本轮进行了操作
                    move = true;
                    lastId[data[0]] = id;
                    sb.append((char) (data[0] + 'a'));
                    --data[1];
                    ++i;
                    //集齐k个本轮结束
                    if (sb.length()%k==0) {
                        break;
                    }
                }
                
                //数量变化，重新排
                list.sort((a,b)->b[1]-a[1]);
            }
 
            return sb.length()==n?sb.toString():"";
        }
    }