0358. Rearrange String k Distance Apart

https://leetcode.com/problems/rearrange-string-k-distance-apart

Description

Given a string s and an integer k, rearrange s such that the same characters are at least distance k from each other. If it is not possible to rearrange the string, return an empty string "".

Example 1:

**Input:** s = "aabbcc", k = 3
**Output:** "abcabc"
**Explanation:** The same letters are at least a distance of 3 from each other.

Example 2:

**Input:** s = "aaabc", k = 3
**Output:** ""
**Explanation:** It is not possible to rearrange the string.

Example 3:

**Input:** s = "aaadbbcc", k = 2
**Output:** "abacabcd"
**Explanation:** The same letters are at least a distance of 2 from each other.

Constraints:

• 1 <= s.length <= 3 * 105

• s consists of only lowercase English letters.

• 0 <= k <= s.length

ac: priority queue greedy

class Solution {
    public String rearrangeString(String s, int k) {
        // Edge cases
        if (s == null || s.length() == 0 || k == 0) {
            return s;
        }
        
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
        }
        
        PriorityQueue<Node> q = new PriorityQueue<>((a, b) -> a.count == b.count ? a.c - b.c : b.count - a.count);
        for (int i = 0; i < count.length; i++) {
            if (count[i] == 0) continue;
            Node node = new Node((char)('a' + i), count[i]);
            q.offer(node);
        }
        
        Queue<Node> kBuffer = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            Node curr = q.poll();
            sb.append(curr.c);
            curr.count--;
            kBuffer.offer(curr); // Add to buffer anyway, because kBuffer size is a time counter.
            
            if (kBuffer.size() >= k) {
                // Node in buffer has wait k time, can join the pool again.
                Node candidate = kBuffer.poll();
                if (candidate.count > 0) q.offer(candidate);
            }
        }
        
        return sb.length() == s.length() ? sb.toString() : "";
    }
    
    class Node {
        char c;
        int count;
        Node(char c, int count) {
            this.c = c;
            this.count = count;
        }
    }
}
/*
Intuition: we have a pool of chars to choose from, always choose the most frequent one first.
When a char is used, it has to wait k time to join the pool again.

O(Nlog26) -> O(N) time, O(N) space
*/