Approach Summary
Max-heap by frequency. Always pick the most frequent char that is different from the last placed. If impossible (max freq > (n+1)/2), return "".
How to Recognize This Pattern
- "Rearrange so no two adjacent chars are equal"
- Greedy: always place the most common remaining char
Complexity Analysis
Time Complexity
O(n log k)
Space Complexity
O(k)
Tags
Hash Table String Greedy Sorting Heap Counting