Code Implementation

import heapq
from collections import Counter, deque

def rearrangeString(s: str, k: int) -> str:
    if k == 0:
        return s

    freq = Counter(s)
    maxHeap = [(-cnt, ch) for ch, cnt in freq.items()]
    heapq.heapify(maxHeap)
    queue = deque()  # stores (cnt, ch, ready_time)
    res = []
    time = 0

    while maxHeap or queue:
        if maxHeap:
            cnt, ch = heapq.heappop(maxHeap)
            res.append(ch)
            if -cnt > 1:
                queue.append((cnt + 1, ch, time + k))
        else:
            # idle slot needed
            if queue:
                res.append('')
            else:
                break

        time += 1
        # if the front of the queue is ready to be pushed back into heap
        if queue and queue[0][2] == time:
            ready_cnt, ready_ch, _ = queue.popleft()
            heapq.heappush(maxHeap, (ready_cnt, ready_ch))

    result = ''.join(res)
    return result if len(result) == len(s) else ""
      

#include <string>
#include <queue>
#include <unordered_map>
#include <vector>

using namespace std;

string rearrangeString(string s, int k) {
    if (k == 0) return s;
    unordered_map<char, int> freq;
    for (char c : s) freq[c]++;
    priority_queue<pair<int, char>> maxHeap;
    for (auto& p : freq)
        maxHeap.push({p.second, p.first});
    queue<pair<int, char>> waitQueue;
    string result;
    while (!maxHeap.empty()) {
        vector<pair<int, char>> temp;
        int cnt = min(k, (int)s.size() - (int)result.size());
        for (int i = 0; i < cnt; ++i) {
            if (maxHeap.empty()) {
                if (temp.empty()) return result;
                return "";
            }
            auto top = maxHeap.top(); maxHeap.pop();
            result += top.second;
            if (--top.first > 0) temp.push_back(top);
        }
        for (auto& p : temp)
            maxHeap.push(p);
    }
    return result.size() == s.size() ? result : "";
}
      

import java.util.*;

public class Solution {
    public String rearrangeString(String s, int k) {
        if (k == 0) return s;
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray())
            freq.put(c, freq.getOrDefault(c, 0) + 1);

        PriorityQueue<Map.Entry<Character, Integer>> maxHeap =
            new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        maxHeap.addAll(freq.entrySet());

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

        while (!maxHeap.isEmpty()) {
            List<Map.Entry<Character, Integer>> temp = new ArrayList<>();
            int cnt = Math.min(k, s.length() - result.length());
            for (int i = 0; i < cnt; i++) {
                if (maxHeap.isEmpty()) {
                    if (temp.isEmpty()) return result.toString();
                    return "";
                }
                Map.Entry<Character, Integer> entry = maxHeap.poll();
                result.append(entry.getKey());
                if (entry.getValue() - 1 > 0) {
                    entry.setValue(entry.getValue() - 1);
                    temp.add(entry);
                }
            }
            maxHeap.addAll(temp);
        }
        return result.length() == s.length() ? result.toString() : "";
    }
}
      

function rearrangeString(s, k) {
    if (k === 0) return s;
    const freq = {};
    for (const ch of s) {
        freq[ch] = (freq[ch] || 0) + 1;
    }
    const maxHeap = [];
    for (const ch in freq) {
        maxHeap.push([freq[ch], ch]);
    }
    maxHeap.sort((a, b) => b[0] - a[0]);
    const res = [];
    while (maxHeap.length) {
        const wait = [];
        let cnt = Math.min(k, s.length - res.length);
        for (let i = 0; i < cnt; ++i) {
            if (!maxHeap.length) {
                if (wait.length === 0) return res.join('');
                return '';
            }
            let [count, ch] = maxHeap.shift();
            res.push(ch);
            if (--count > 0) wait.push([count, ch]);
        }
        for (const item of wait) maxHeap.push(item);
        maxHeap.sort((a, b) => b[0] - a[0]);
    }
    return res.length === s.length ? res.join('') : '';
}
      

Problem Description

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

• Each character from s must be used exactly as many times as it appears in the input.
• The returned string must have the same length as s if a valid rearrangement is possible.
• If multiple valid answers exist, any one is acceptable.
• If it is impossible to rearrange, return "".

Example:
Input: s = "aabbcc", k = 3
Output: "abcabc" (or any other string where same letters are at least 3 apart)

Thought Process

At first glance, this problem looks like a permutation or rearrangement task. A brute-force approach would be to try every possible permutation of the string and check if the k-distance condition is met, but this is computationally infeasible for even moderate string lengths.

Instead, we need to organize the placement of characters so that the most frequent ones are spaced out as much as possible. A natural analogy is scheduling: the most "demanding" tasks (characters with the highest frequency) must be given enough "cooldown" time between appearances. If we always pick the most frequent character that is allowed (i.e., that is not in its cooldown), we can greedily build a valid string.

To do this efficiently, we need to:

• Track how many times each character still needs to be placed.
• Always pick the character with the highest remaining count that is allowed (not within its cooldown window).
• Manage a cooldown for recently used characters.

Solution Approach

Here is a step-by-step guide to the optimized solution:

1. Count Character Frequencies:
   • Use a hash map to count how many times each character appears in s.
2. Build a Max-Heap:
   • Insert each character into a max-heap (priority queue), prioritized by frequency (most frequent first).
   • This helps us always pick the character that needs the most spacing.
3. Cooldown Queue:
   • Use a queue to keep track of characters that have been recently used and are "cooling down".
   • Each entry in the queue contains the character, its remaining count, and the earliest time it can be used again.
4. Rebuild the String:
   • At each step, pick the most frequent character from the heap that is not cooling down.
   • Append it to the result string and decrease its count.
   • If its count is still greater than zero, add it to the cooldown queue with a timestamp indicating when it can be used again (current step + k).
   • If the cooldown queue's front item is ready to be used again, push it back into the heap.
   • If there is no character available to use and the cooldown queue is not empty, we must insert an idle slot (which means rearrangement is impossible), so we return "".
5. Check for Completion:
   • If the result string is the same length as the input, return it.
   • Otherwise, return "" (impossible to rearrange).

Why these choices?

• The max-heap lets us always pick the character that "needs" the most spacing, helping to avoid impossible situations later.
• The queue manages the cooldown efficiently, so we never break the k-distance rule.

Example Walkthrough

Let's use the input s = "aabbcc", k = 3.

1. Frequencies: {'a': 2, 'b': 2, 'c': 2}
2. Max-Heap: [('a', 2), ('b', 2), ('c', 2)]
3. Step 1: Pick 'a' (now 1 left), add to result: a, cooldown queue: [('a', 1, 3)]
4. Step 2: Pick 'b' (now 1 left), result: ab, cooldown queue: [('a', 1, 3), ('b', 1, 4)]
5. Step 3: Pick 'c' (now 1 left), result: abc, cooldown queue: [('a', 1, 3), ('b', 1, 4), ('c', 1, 5)]
6. Step 4: Now, time is 3. 'a' is ready (cooldown expired), pick 'a' again (now 0 left), result: abca, cooldown queue: [('b', 1, 4), ('c', 1, 5)]
7. Step 5: 'b' is ready, pick 'b' (now 0 left), result: abcab, cooldown queue: [('c', 1, 5)]
8. Step 6: 'c' is ready, pick 'c' (now 0 left), result: abcabc, cooldown queue: []

All characters used, and each same character is at least 3 apart. Success!

Time and Space Complexity

Brute-force approach:

• Would try all permutations: O(n!) time, which is impractical for n > 8-10.

• Let n be the length of s, and d the number of unique characters.
• Each heap operation is O(log d), and each character is pushed/popped at most its frequency times.
• Total time: O(n log d).
• Space: O(d) for the heap, O(d) for the cooldown queue, and O(n) for the result string.

In practice, both time and space are efficient and scalable for typical input sizes.

Summary

To rearrange a string so that no two identical characters are less than k apart, we use a max-heap to always pick the most frequent available character, and a queue to manage cooldowns. This greedy approach ensures that the hardest-to-place characters are spaced out first, avoiding impossible arrangements later. The algorithm is efficient and elegant, leveraging priority queues and queues for optimal scheduling, and is a classic example of greedy + heap-based design for string rearrangement under constraints.