My code:

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

reference:
http://www.programcreek.com/2014/08/leetcode-rearrange-string-k-distance-apart-java/

这道题目直接看的答案，用的
PriorityQueue + HashMap

pq 的优先级是，出现频率越大的字母，优先级越高。

然后我把所有字母插入pq，相同字母只插入一次。
第一次，按照距离至少是k来插入。
所以 cnt = Math.min(k, len);

然后把除了出现这次外，还会出现的字母，再次插入到queue中
以此类推。

Anyway, Good luck, Richardo! -- 10/09/2016