Given a non-empty stringsand an integerk, rearrange the string such that the same characters are at least distancekfrom each other.

All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string"".

Example 1:

s = "aabbcc", k = 3

Result: "abcabc"

The same letters are at least distance 3 from each other.

Example 2:

s = "aaabc", k = 3 

Answer: ""

It is not possible to rearrange the string.

Example 3:

s = "aaadbbcc", k = 2

Answer: "abacabcd"

Another possible answer is: "abcabcda"

The same letters are at least distance 2 from each other.

Credits:
Special thanks to@elmirapfor adding this problem and creating all test cases.

class Solution {
    public String rearrangeString(String s, int k) {
        if (s == null || s.length() == 0 || k == 0) return s;

        Map<Character, Integer> hash = new HashMap<>();
        for (Character c : s.toCharArray()){
            hash.put(c, hash.getOrDefault(c, 0) + 1);
        }

        PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>((a, b) -> (b.getValue() - a.getValue()));
        pq.addAll(hash.entrySet());

        StringBuilder sb = new StringBuilder();
        Queue<Map.Entry<Character, Integer>> q = new LinkedList<>();

        while (!pq.isEmpty()){
            Map.Entry<Character, Integer> cur = pq.poll();
            sb.append(cur.getKey());
            cur.setValue(cur.getValue() - 1);
            q.offer(cur);

            while (q.size() >= k){
                Map.Entry<Character, Integer> temp = q.poll();
                //System.out.println("temp: " + temp.getKey() + " " + temp.getValue());
                if (temp != null && temp.getValue() > 0){
                    pq.offer(temp);
                }
            }
        }

        //System.out.println("check sb: " + sb.toString());
        return sb.length() == s.length() ? sb.toString() : "";
    }
}