358. Rearrange String k Distance Apart

Version #1 Greedy
Always append the char of most count
Use wait list to hold chars that need cool down time
[2ND TRY]
When the items in the waiting queue has satisfied the k limit, we check if its remaining count is larger than 0 or not. Only push back to maxHeap if its remaining count is larger than 0

class Solution {
    public String rearrangeString(String s, int k) {
        if (k == 0) return s;
// abacabcd
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
int index = s.charAt(i) - 'a';
if (count[index] > s.length() / k + 1) return "";
count[index]++;
}
// int[0] -> char index in 26, int[1] -> remaining count
PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[1] - a[1]);
for (int i = 0; i < 26; i++) {
if (count[i] > 0) {
maxHeap.offer(new int[]{i, count[i]});
}
}
StringBuilder sb = new StringBuilder();
Queue<int[]> waitingQue = new LinkedList<>();
while (!maxHeap.isEmpty()) {
int[] curr = maxHeap.poll();
curr[1]--;
sb.append((char) (curr[0] + 'a'));
waitingQue.offer(curr);
if (waitingQue.size() >= k) {
int[] back = waitingQue.poll();
if (back[1] > 0) {
maxHeap.offer(back);
}
}
}
return sb.length() == s.length() ? sb.toString() : "";
// return sb.toString();
}
}

[1ST TRY]
int[]
8.45 %
class Solution {
    public String rearrangeString(String s, int k) {
        // Every time we are trying to arrange the char with the most count
        int[] map = new int[26];
        for (int i = 0; i < s.length(); i++) {
            map[s.charAt(i) - 'a']++;
        }
        // index is char, value is count
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (int i = 0; i < 26; i++) {
            if (map[i] > 0) maxHeap.offer(new int[]{i, map[i]});
        }
        Queue<int[]> que = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        while (!maxHeap.isEmpty()) {
            int[] curr = maxHeap.poll();
            // System.out.println(curr[0] + " " + curr[1]);
            sb.append((char)('a' + curr[0]));
            curr[1]--;
            que.offer(curr);
            if (que.size() >= k) {
                int[] item = que.poll();
                if (item[1] > 0) maxHeap.offer(item);
            }
         
        }
        return sb.length() == s.length() ? sb.toString() : "";
    }
}




Map.Entry

class Solution {
    public String rearrangeString(String s, int k) {
        // Every time we are trying to arrange the char with the most count
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, 1 + map.getOrDefault(c, 0));
        }
        PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        maxHeap.addAll(map.entrySet());
        Queue<Map.Entry<Character, Integer>> que = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        while (!maxHeap.isEmpty()) {
            Map.Entry<Character, Integer> curr = maxHeap.poll();
            // System.out.println(curr.getKey() + " " + curr.getValue());
            sb.append(curr.getKey());
            curr.setValue(curr.getValue() - 1);
            que.offer(curr);
            if (que.size() < k) continue;
            Map.Entry<Character, Integer> item = que.poll();
            if (item.getValue() > 0) maxHeap.offer(item);
        }
        return sb.length() == s.length() ? sb.toString() : "";
    }
}