358. K distance interval rearrange string sorting

358. K The distance interval rearranges the string

Give you a non empty string  s  And an integer  k , You have to put this string  s  Rearrange the letters in , Make the position spacing of the same letters in the rearranged string   At least   by  k . If you can't do it , Please return an empty string  "".

Example 1：

 Input : s = "aabbcc", k = 3
 Output : "abcabc" 
 explain :  The same letters are spaced at least in the new string  3  Unit distance .

Example 2:

 Input : s = "aaabc", k = 3
 Output : "" 
 explain :  There is no way to find possible rearrangement results .

Example  3:

 Input : s = "aaadbbcc", k = 2
 Output : "abacabcd"
 explain :  The same letters are spaced at least in the new string  2  Unit distance .

Tips ：

• 1 <= s.length <= 3 * 10^5
• s  It's only made up of lowercase letters
• 0 <= k <= s.length

The result of doing the question

success , Priority queue , Sliding windows are useless , Pure sort + Array + aggregate （ It's OK not to , Just plain arrays ）

Method ： Sort

1. There is a length of n String , Every time k Divide into groups , It can be divided out part=(n+k-1) Group , If there are more than characters part, Must not form a template string , Go straight back to

2. Letters are counted in an array , Record the number of each character

3. Longer than 0 Put into the list , Reverse by quantity

4. Take as many as possible each time k The characters of , Put in the answer

5. Need to check the index position , If it is too close to the front , Then try the same number of other letters

6. Make a sequence each time （ Only the length of the 26, So it doesn't matter if you've been waiting ）

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;// The maximum number of each part 

            for(int i = 0; i < n; i++){
                int index = s.charAt(i)-'a';
                arr[index]++;
                if(arr[index]>part){
                    return "";
                }
            }

            // In reverse order of quantity 
            List<int[]> list = new ArrayList<>();
            for(int i = 0; i < 26; i++){
                if(arr[i]>0){
                    list.add(new int[]{i,arr[i]});// Letter , Number 
                }
            }

            // Reverse by quantity 
            list.sort((a,b)->b[1]-a[1]);

            int[] lastId = new int[26];// Last index bit 
            Arrays.fill(lastId,-1);
            StringBuilder sb = new StringBuilder();
            boolean move = true;
            for(int i = 0; i < n&&move; ){
                move = false;
                // From more to less 
                for (int[] data : list) {
                    // Jump out if you don't score 
                    if (data[1] == 0) break;

                    int id = sb.length();
                    // Not far enough , skip 
                    if(lastId[data[0]]!=-1 && id-lastId[data[0]]<k)
                        continue;
                    // This round has been operated 
                    move = true;
                    lastId[data[0]] = id;
                    sb.append((char) (data[0] + 'a'));
                    --data[1];
                    ++i;
                    // Gather together k This round ends 
                    if (sb.length()%k==0) {
                        break;
                    }
                }
                
                // Quantity change , Rearrange 
                list.sort((a,b)->b[1]-a[1]);
            }

            return sb.length()==n?sb.toString():"";
        }
    }