358. Rearrange String k Distance Apart

/*
Time Complexity: O(N logN)
Space Complexity: O(N)
N = length of the string.
*/
class Solution {
    public String rearrangeString(String s, int k) {
        if (s == null || s.length() == 0) {
            return "";
        }
        if (s.length() == 1 || k == 0) {
            return s;
        }

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

        PriorityQueue<Map.Entry<Character, Integer>> queue = new PriorityQueue<Map.Entry<Character, Integer>>(
            (a,b) -> (a.getValue() == b.getValue() ? a.getKey() - b.getKey() : b.getValue() - a.getValue()));
        queue.addAll(map.entrySet());

        StringBuilder sb = new StringBuilder();

        while (!queue.isEmpty()) {
            int n = k;
            List<Map.Entry<Character, Integer>> waitingList = new LinkedList();
            while (n > 0 && !queue.isEmpty()) {
                Map.Entry<Character, Integer> topEntry = queue.poll();
                sb.append(topEntry.getKey());
                topEntry.setValue(topEntry.getValue() - 1);
                waitingList.add(topEntry);
                n--;
            }
            for (Map.Entry<Character, Integer> entry : waitingList) {
                if (entry.getValue() > 0) {
                    queue.offer(entry);
                }
            }
            if (n > 0 && !queue.isEmpty()) {
                return "";
            }
            waitingList.clear();
        }
        return sb.toString();
    }
}


/*
Above solution does not worn in leetcode. Thus replacing the ArrayList with a queue.

Time Complexity: O(N logN)
Space Complexity: O(N)
N = length of the string.
*/
class Solution {
    public String rearrangeString(String s, int k) {
        if (s == null || s.length() == 0) {
            return "";
        }
        if (s.length() == 1 || k == 0) {
            return s;
        }

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

        PriorityQueue<Map.Entry<Character, Integer>> queue = new PriorityQueue<Map.Entry<Character, Integer>>(
            (a,b) -> (a.getValue() == b.getValue() ? a.getKey() - b.getKey() : b.getValue() - a.getValue()));
        queue.addAll(map.entrySet());

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

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

            if (waitingList.size() < k) {
                continue;
            }

            Map.Entry<Character, Integer> front = waitingList.poll();
            if (front.getValue() > 0) {
                queue.offer(front);
            }
        }
        return sb.length() == s.length() ? sb.toString() : "";
    }
}