Reorganize String
Rearrange a string so no two adjacent characters are the same using a max-heap.
Reorganize String
Problem: Given a string s, rearrange its characters so that no two adjacent characters are the same. Return any valid rearrangement, or an empty string if it's impossible.
Example:
- Input:
s = "aab" - Output:
"aba"— no two adjacent 'a's - Input:
s = "aaab"→ Output:""— impossible (too many 'a's)
Note
It's impossible only when the most frequent character appears more than (n+1)/2 times. Otherwise, always greedily place the most frequent unused character — as long as it's different from the last one placed.
How to Think About It
Starting point: Try every permutation and check if it's valid. O(n!) — completely infeasible past a few characters.
Feasibility check first: Before building anything, ask: is this even possible? If any character appears more than (n+1)/2 times, there aren't enough gaps to place it without adjacency. Return "" immediately.
Greedy insight: At each position, what's the safest character to place? The most frequent one that isn't the same as the last character placed. Why the most frequent? Because the character that threatens to make the problem unsolvable (by running out of gaps) is the one with the highest count. Placing it now keeps counts balanced.
Why a max-heap? You need the most frequent available character at each step. A max-heap keyed by frequency gives you that in O(log k). Pop the top two characters, place the first, push the second back (if count > 0), then push the first back (decremented, if count > 0). This ensures you always use the most frequent available character that differs from the last placed.
The pattern: Greedy + max-heap for "always pick the best available option at each step" problems.
Brute Force
View Brute Force
Optimal — Max-Heap (Greedy)
View Optimal Solution
| Approach | Time | Space |
|---|---|---|
| Try all permutations | O(n!) | O(n) |
| Max-Heap (greedy) | O(n log k) | O(n) |