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.
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) |