MediumNeetCode150Hash TableGreedyHeap (Priority Queue)String
Reorganize String
Rearrange so no adjacent characters are same.
Examples
Input
s = "aab"
Output
aba
Rearranged to avoid adjacent duplicates.
Constraints
- •
1 <= s.length <= 500 - •
s consists of lowercase English letters
Approaches
Try all arrangements.
CodeT: O(n!) | S: O(n) recursion stack
Place most frequent first.
CodeT: O(n log k) | S: O(k) heap k=unique chars
Count, sort by freq, fill even positions.
CodeT: O(n) | S: O(k) count array
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Backtracking | O(n!) | O(n) recursion stack | Try all arrangements. |
| Greedy + Heap | O(n log k) | O(k) heap k=unique chars | Place most frequent first. |
| Greedy + Count | O(n) | O(k) count array | Count, sort by freq, fill even positions. |
Backtracking
T: O(n!)S: O(n) recursion stack
Try all arrangements.
Greedy + Heap
T: O(n log k)S: O(k) heap k=unique chars
Place most frequent first.
Greedy + Count
T: O(n)S: O(k) count array
Count, sort by freq, fill even positions.
Common Mistakes
Not checking impossible case
Wrong placement order
Off-by-one in even/odd fill