Leetcode: Rearrange String k Distance Apart

This question is asked at Facebook and Microsoft. Here is the question: 

Given a String s and Integer K, rearrange S such that the same characters are at least distance k from each other, or return an empty string. 

Here are some strings:

Input: s = "aabbcc", 

k = 3

 Output: "abcabc" 

Explanation: The same letters are at least a distance of 3 from each other.

Input: s = "aaabc",

k = 3 Output: "" 

Explanation: It is not possible to rearrange the string.

We obviously need to use both a map and priorityqueue to solve this problem. We'll use a greedy algorithm to solve this. For each step, we select the character with the highest remaining count if possible. A regular queue is used to "freeze" previous appeared character in the period of k. 

Basically we know that at least we know the frequency of each character, so we use a map and a character to map the frequency of each data structure. Then we try to append the most frequent characters first, which then we can use a heap to know the most frequent item. We use a max heap and sort the frequency lexicographically. 

We also need a list to keep track of the character properly and poll from the heap. We want to check to see if we have unused characters and reoffer these to the heap. We can use int array or int array the size of 26. But using the int[] array is time efficient. 

class Solution {

    public String rearrangeString(String s, int k) {

        //map, char: int

        //no separator needed, so return the string. 

        if (k == 0 || s.length < k) return s;

        int[] map = new int[26];

        //add the frequency in the map. 

        for(char c: s.toCharArray()) {

            map[c - 'a']++;

        }

        //added a map with the character and the occurrences and sorted by occurrence then character in reverse alphabetical order. 

        PriorityQueue<int[]> heap = new PrioriyQueue<>( (a, b) -> a[1] == b[1] ? a[0] - b[0] : b[1] - a[1]);

        for(int i = 0; i < 26; i++) {

            if(map[i] > 0) {

                heap.offer(int[]{i, map[i]});

            }

        }

        StringBuilder sb = new StringBuilder(); 

        while(!heap.isEmpty()) {

            List<Integer> list = new ArrayList<>(); 

            for(int i = 0; i < k; i++) {

                //poll

                int[] cur = heap.poll();

                //append everything to the stringbuilder. 

                sb.append((char) (cur[0] + 'a'));

                //add character to the list. 

                list.add(cur[0]);

                //return string if heap is empty and we have a different stringbuilder length, so invaid string. 

                if(heap.size() == 0) {

                    if(i != k - 1 && sb.length() != s.length()) return "";

                    break;

                }

            }

            for(int i : list) {

                if(--map[i] > 0) {

                    //offer a new array element to the heap if there is more map elements. 

                    heap.offer(new int[]{i, map[i]});

                }

            }

        }

    return sb.toString(); 

    }

}

We utilize the frequency of the array. We add frequency in the map and using a hash map select a character and see if it's valid. If it's valid we'll add more characters until the heap is empty.