Rearrange String k Distance Apart

Rearrange String k Distance Apart

What is this problem about?

The Rearrange String k Distance Apart problem asks you to rearrange a string so that the same characters are at least k positions apart. Return the rearranged string, or an empty string if it's impossible. This hard coding problem uses a greedy max-heap approach with a cooldown queue. The hash table, counting, sorting, heap, string, and greedy interview pattern is fully tested.

Why is this asked in interviews?

Amazon, TikTok, and Google ask this because it's the canonical greedy task-scheduling problem applied to strings. The solution demonstrates heap-based greedy with a cooldown window — directly modeling CPU scheduling with cooling periods.

Algorithmic pattern used

Max-heap + cooldown queue. Use a max-heap of (frequency, character). A deque (cooldown queue) holds characters that must wait k steps before being reused. At each step: pop the highest-frequency character from heap, append to result, decrement its frequency, add to cooldown queue with a "release time" (current_step + k). When the front of the deque has reached its release time, push it back to the heap.

Example explanation

s="aaabc", k=2. Frequencies: {a:3,b:1,c:1}. Heap: [(3,a),(1,b),(1,c)].

• Step 0: pop 'a'(3→2). result="a". Cooldown: [('a',2,2)].
• Step 1: pop 'b'(1→0). result="ab". Cooldown: [('a',2,2),('b',0,3)].
• Step 2: 'a' cooldown releases. Pop 'a'(2→1). result="aba". Cooldown: [('a',1,4)].
• Step 3: pop 'c'(1→0). result="abac". Cooldown releases 'a'.
• Step 4: pop 'a'(1→0). result="abaac"? Wait... Result: "abaca" or similar valid arrangement.

Common mistakes candidates make

• Not using a cooldown mechanism (placing same characters < k apart).
• Using a simple deque without tracking release times.
• Returning partial result when heap is empty but cooldown still has characters (→ invalid, return "").
• Off-by-one in k distance (k=2 means at least 2 apart, not 2 steps between).

Interview preparation tip

Rearrange String k Distance Apart is the string variant of the Task Scheduler problem. The cooldown deque pattern is universal: place processed items in a "waiting zone" for exactly k steps, then release back to the main heap. Practice both problems together. If the result length < original string length, the arrangement is impossible — return "".