Given a non-empty string str 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:
str = "aabbcc", k = 3

Result: "abcabc"

The same letters are at least distance 3 from each other.
Example 2:
str = "aaabc", k = 3 

Answer: ""

It is not possible to rearrange the string.
Example 3:
str = "aaadbbcc", k = 2

Answer: "abacabcd"

Another possible answer is: "abcabcda"

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

Solution

public class Solution {
    public class Occur {
        public char c;
        public int cnt;
        public Occur(char c, int cnt) {this.c = c; this.cnt = cnt;}
    }

    public String rearrangeString(String str, int k) {

        if(k <= 0) return str;

        // sort by occurence
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for(char c: str.toCharArray()) {
            if(!map.containsKey(c)) map.put(c, 0);
            map.put(c, map.get(c) + 1);
        }

        Queue<Occur> candidate = new PriorityQueue<Occur>(new Comparator<Occur>() {
                public int compare(Occur o1, Occur o2) {
                    return -Integer.compare(o1.cnt, o2.cnt);
                }
            }
        );

        for(Character c: map.keySet()) {
            candidate.offer(new Occur(c, map.get(c)));
        }

        // maintain a window of K to maintain available insert
        boolean inwindow[] = new boolean[128];
        char output[] = new char[str.length()];
        for(int i = 0; i < str.length(); i++) {
            List<Occur> occurList = new ArrayList<Occur>();

            if(i >= k) inwindow[output[i - k]] = false;
            boolean found = false;

            // find a available char
            while(!candidate.isEmpty()) {
                Occur occur = candidate.poll();    

                if(occur.cnt > 0 && !inwindow[occur.c]) {
                    occur.cnt--;
                    inwindow[occur.c] = true;
                    output[i] = occur.c;
                    found = true;

                    if(occur.cnt > 0) occurList.add(occur);
                    break;
                } else {
                    occurList.add(occur);
                }
            }

            if(!found) return "";
            candidate.addAll(occurList);
        }

        return new String(output);
    }
}