Rearrange String k Distance Apart

358. Rearrange String k Distance Apart

Given a non-empty string s and an integer k, rearrange the string such that the same characters are at least distance k from 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.

public class Solution {
    public String rearrangeString(String s, int k) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        if (k == 0) {
            return s;
        }
        
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }
        }
        
        PriorityQueue<Character> queue = new PriorityQueue<>(new Comparator<Character>() {
           public int compare(Character c1, Character c2) {
               if (map.get(c1).intValue() != map.get(c2).intValue()) {
                   return map.get(c2) - map.get(c1);
               }
               
               return c1.compareTo(c2);
           }
        });
        
        for (char c : map.keySet()) {
            queue.offer(c);
        }
        
        int len = s.length();
        StringBuilder result = new StringBuilder();
        
        while (!queue.isEmpty()) {
            int count = Math.min(len, k);
            List<Character> list = new ArrayList<>();
            
            for (int i = 0; i < count; i++) {
                if (queue.isEmpty()) {
                    return "";
                }
                
                char c = queue.poll();
                result.append(c);
                len--;
                
                map.put(c, map.get(c) - 1);
                if (map.get(c) > 0) {
                    list.add(c);
                }
            }
            
            for (char c : list) {
                queue.offer(c);
            }
        }
        
        return result.toString();
    }
}

Hope this helps,
Michael