Rearrange String k Distance Apart

hard heap greedy string queue

Problem

Given a string s and an integer k, rearrange s so the same characters are at least k apart. Return any valid arrangement or "" if impossible.

Inputs = "aabbcc", k = 3

Output"abcabc"

Each repeat is ≥ 3 apart.

import heapq
from collections import Counter, deque
def rearrange_string(s, k):
    if k <= 1: return s
    cnt = Counter(s)
    heap = [(-v, ch) for ch, v in cnt.items()]
    heapq.heapify(heap)
    q = deque()
    out = []
    while heap:
        v, ch = heapq.heappop(heap)
        out.append(ch)
        q.append((v + 1, ch))
        if len(q) >= k:
            cv, cc = q.popleft()
            if cv < 0: heapq.heappush(heap, (cv, cc))
    return "".join(out) if len(out) == len(s) else ""

function rearrangeString(s, k) {
  if (k <= 1) return s;
  const cnt = new Map();
  for (const ch of s) cnt.set(ch, (cnt.get(ch) || 0) + 1);
  const heap = [...cnt.entries()].map(([c, v]) => [-v, c]);
  heap.sort();
  function push(p) { heap.push(p); heap.sort(); }
  function pop() { return heap.shift(); }
  const q = [];
  const out = [];
  while (heap.length) {
    const [v, ch] = pop();
    out.push(ch);
    q.push([v + 1, ch]);
    if (q.length >= k) {
      const [cv, cc] = q.shift();
      if (cv < 0) push([cv, cc]);
    }
  }
  return out.length === s.length ? out.join("") : "";
}

class Solution {
    public String rearrangeString(String s, int k) {
        if (k <= 1) return s;
        Map cnt = new HashMap<>();
        for (char c : s.toCharArray()) cnt.merge(c, 1, Integer::sum);
        PriorityQueue heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (var e : cnt.entrySet()) heap.add(new int[]{ e.getValue(), e.getKey() });
        Deque q = new ArrayDeque<>();
        StringBuilder out = new StringBuilder();
        while (!heap.isEmpty()) {
            int[] cur = heap.poll();
            out.append((char) cur[1]);
            q.add(new int[]{ cur[0] - 1, cur[1] });
            if (q.size() >= k) {
                int[] c2 = q.poll();
                if (c2[0] > 0) heap.add(c2);
            }
        }
        return out.length() == s.length() ? out.toString() : "";
    }
}

string rearrangeString(string s, int k) {
    if (k <= 1) return s;
    unordered_map cnt;
    for (char c : s) cnt[c]++;
    priority_queue> heap;
    for (auto& [c, v] : cnt) heap.push({v, c});
    queue> q;
    string out;
    while (!heap.empty()) {
        auto [v, c] = heap.top(); heap.pop();
        out += c;
        q.push({v - 1, c});
        if ((int)q.size() >= k) {
            auto cur = q.front(); q.pop();
            if (cur.first > 0) heap.push(cur);
        }
    }
    return (int)out.size() == (int)s.size() ? out : "";
}

Explanation

The smart move is to always place the character that appears most often next, because the frequent characters are the hardest to keep k apart. A max-heap plus a small cooldown queue handles this cleanly.

We count each character and push (count, char) into a max-heap. Each step we pop the character with the highest remaining count, append it to the answer, decrease its count, and park it in a waiting queue instead of putting it straight back.

A character stays in the queue until k characters have been placed after it. Once the queue length reaches k, the oldest item is released, and if it still has count left, it goes back into the heap. This guarantees the same character is never reused within a window of k.

Example: s = "aabbcc", k = 3. We place a, then b, then c (queue now full). Releasing a lets us place a again, then b, then c, giving "abcabc".

If at some point the heap is empty but we have not used every character (a character still waits in the queue), the arrangement is impossible, so we return "".

Time: O(n log σ) Space: O(σ)