Reorganize String

Reorganize String

What is this problem about?

The Reorganize String interview question asks you to rearrange a given string so that no two adjacent characters are the same. If it is possible to do so, return any valid rearrangement; otherwise, return an empty string. This is a classic greedy problem using a max-heap to always place the most frequent available character.

Why is this asked in interviews?

This problem is asked at Apple, Uber, Goldman Sachs, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe because it combines character frequency analysis with a priority queue to achieve an optimal greedy strategy. It is a key problem in the "task scheduling" and "interleaving" family. Mastering this problem directly prepares you for problems like Task Scheduler and Rearrange String K Distance Apart.

Algorithmic pattern used

The pattern is greedy with a max-heap (priority queue). Count character frequencies. Build a max-heap of (-freq, char) pairs. At each step, pop the most frequent character and append it to the result. If the previous character is still available (its frequency > 0), push it back into the heap after placing the current character. This "cooldown" of one step ensures no two adjacent characters are the same. If the heap is exhausted before the result is complete, the arrangement is impossible.

Example explanation

Input: "aab" — frequencies: a=2, b=1. Max-heap: [(-2,'a'), (-1,'b')].

• Pop a (freq=2). Result: "a". Hold a with remaining freq=1.
• Pop b (freq=1). Result: "ab". Push back a (freq=1). Heap: [(-1,'a')].
• Pop a (freq=1). Result: "aba". No held character.

Output: "aba".

If input were "aaa", after placing one a there's no other character to interleave — heap empties with a still held → return "".

Common mistakes candidates make

• Not holding the previously placed character and pushing it back too early, which creates adjacent duplicates.
• Returning "" for any string without checking if max_freq > (len+1)//2 first — a quick early exit is cleaner.
• Using a min-heap with positive frequencies instead of a max-heap with negated frequencies.
• Forgetting that multiple valid outputs exist — return any one of them.

Interview preparation tip

For the Reorganize String coding problem, the heap (priority queue), counting, and greedy interview pattern is central. Practice the "hold and re-insert" mechanism — it is the key non-obvious step. Interviewers at Citadel and Salesforce often ask for the mathematical condition when a solution is impossible: if any character appears more than (n+1)//2 times, return "" immediately. This condition check as an early exit demonstrates deep problem understanding.