1. Priority Queue

Intuition

The key insight is that we should always place the character with the highest remaining frequency next. This greedy approach maximizes our chances of success because using up high-frequency characters early gives us more flexibility later.

However, after placing a character, we cannot use it again until at least k positions have passed. To handle this constraint, we use a "cooldown" queue that holds recently used characters along with the index where they were placed. Once enough positions have passed, the character becomes available again and returns to the priority queue.

If at any point we have no available characters to place (the priority queue is empty while we still need more characters), it means rearrangement is impossible.

Algorithm

1. Count the frequency of each character in the string.
2. Insert all characters with their frequencies into a max heap (priority queue), prioritized by frequency.
3. Initialize an empty result string and a "busy" queue to track characters in their cooldown period.
4. While the result is not complete:
   • Check if the character at the front of the busy queue has completed its cooldown (at least k positions since last use). If so, move it back to the priority queue.
   • If the priority queue is empty, return an empty string (rearrangement is impossible).
   • Pop the character with the highest frequency from the priority queue and append it to the result.
   • Decrement its frequency. If it still has remaining occurrences, add it to the busy queue with the current index.
5. Return the constructed result string.

class Solution {
    public String rearrangeString(String s, int k) {
        Map<Character, Integer> freq = new HashMap<>();
        // Store the frequency for each character.
        for (char c : s.toCharArray()){
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }
        
        PriorityQueue<Pair<Integer, Character>> free=
                    new PriorityQueue<Pair<Integer, Character>>((a, b) -> b.getKey() - a.getKey());

        // Insert the characters with their frequencies in the max heap.
        for (char c : freq.keySet()){
            free.offer(new Pair<>(freq.get(c), c));
        }
        
        StringBuffer ans = new StringBuffer();
        // This queue stores the characters that cannot be used now.
        Queue<Pair<Integer, Character>> busy = new LinkedList<>();
        while (ans.length() != s.length()) {
            int index = ans.length();
            
            // Insert the character that could be used now into the free heap.
            if (!busy.isEmpty() && (index - busy.peek().getKey()) >= k) {
                Pair<Integer, Character> q = busy.remove();
                free.offer(new Pair<>(freq.get(q.getValue()), q.getValue()));
            }
            
            // If the free heap is empty, it implies no character can be used at this index.
            if (free.isEmpty()) {
                return "";
            }
            
            Character currChar = free.peek().getValue();
            free.remove();
            ans.append(currChar);
            
            // Insert the used character into busy queue with the current index.
            freq.put(currChar, freq.get(currChar) - 1);
            if (freq.get(currChar) > 0) {
                busy.add(new Pair<>(index, currChar));
            }
        }
        
        return ans.toString();
    }
}

Time & Space Complexity

• Time complexity: $O((N + K) \log K)$
• Space complexity: $O(K)$

Where $N$ is the length of the string s, and $K$ is the number of unique characters in the string s.

---

2. Greedy

Intuition

Instead of simulating character placement one by one, we can think of the problem in terms of segments. If the maximum frequency of any character is maxFreq, we need at least maxFreq segments. Characters with the highest frequency must appear in every segment, while those with lower frequencies can be distributed across fewer segments.

The idea is to first place all high-frequency characters (those appearing maxFreq or maxFreq - 1 times) into their respective segments, ensuring they are spaced apart. Then, distribute the remaining characters in a round-robin fashion across the first maxFreq - 1 segments.

For the arrangement to be valid, each of the first maxFreq - 1 segments must have at least k characters. The last segment can be shorter since no character needs to maintain distance after it.

Algorithm

1. Count the frequency of each character and find the maximum frequency maxFreq.
2. Identify characters with frequency equal to maxFreq (most frequent) and maxFreq - 1 (second most frequent).
3. Create maxFreq segments. Place one instance of each "most frequent" character in every segment, and one instance of each "second most frequent" character in all but the last segment.
4. Distribute the remaining characters (those with frequency less than maxFreq - 1) across the first maxFreq - 1 segments in round-robin order.
5. Verify that each of the first maxFreq - 1 segments has at least k characters. If not, return an empty string.
6. Concatenate all segments and return the result.

class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        freqs = Counter(s)
        max_freq = max(freqs.values()) if freqs else 0
        
        # Store all the characters with the highest and second highest frequency
        most_chars = set()
        second_chars = set()
        
        for char, freq in freqs.items():
            if freq == max_freq:
                most_chars.add(char)
            elif freq == max_freq - 1:
                second_chars.add(char)
        
        # Create max_freq number of different strings
        segments = [[] for _ in range(max_freq)]
        
        # Insert one instance of characters with frequency max_freq & max_freq - 1 in each segment
        for i in range(max_freq):
            for c in most_chars:
                segments[i].append(c)
            
            # Skip the last segment as the frequency is only max_freq - 1
            if i < max_freq - 1:
                for c in second_chars:
                    segments[i].append(c)
        
        segment_id = 0
        
        # Iterate over the remaining characters and distribute instances over segments
        for char, freq in freqs.items():
            # Skip characters with max_freq or max_freq - 1 frequency
            if char in most_chars or char in second_chars:
                continue
            
            # Distribute the instances over segments in round-robin manner
            for _ in range(freq):
                segments[segment_id].append(char)
                segment_id = (segment_id + 1) % (max_freq - 1)
        
        # Each segment except the last should have exactly k elements
        for i in range(max_freq - 1):
            if len(segments[i]) < k:
                return ""
        
        # Join all segments and return
        return ''.join(''.join(segment) for segment in segments)

Time & Space Complexity

• Time complexity: $O(N)$
• Space complexity: $O(K)$

Where $N$ is the length of the string s, and $K$ is the number of unique characters in the string s.

---

Common Pitfalls

Ignoring the Edge Case When k Equals Zero or One

When k is 0 or 1, any arrangement is valid since there is no spacing constraint. Failing to handle these cases early can lead to division by zero errors (e.g., segmentId % (maxFreq - 1)) or unnecessary processing.

Reinserting Characters to Priority Queue with Stale Frequencies

In the priority queue approach, after using a character, its frequency decreases. When reinserting it from the cooldown queue back to the priority queue, you must use the updated frequency, not the original. Using stale frequencies causes incorrect ordering and wrong character selection.

Miscalculating the Cooldown Period

The cooldown constraint means the same character cannot appear within k positions of its last occurrence. A common error is using k-1 instead of k for the cooldown check, or vice versa. Carefully verify that (currentIndex - lastUsedIndex) >= k before reusing a character.

Not Detecting Impossible Cases Early

If the maximum frequency character appears more times than can be accommodated given k and the string length, rearrangement is impossible. Failing to detect this early leads to infinite loops or incorrect outputs. Check that each segment (except possibly the last) can contain at least k characters.

Off-by-One Errors in Segment Distribution

When distributing characters across segments in the greedy approach, the last segment has different requirements than the others. Forgetting to skip the last segment when placing maxFreq - 1 frequency characters, or using wrong modular arithmetic for round-robin distribution, causes incorrect results.