Reorganize String - Solution & Explanation

Problem Overview: You are given a string and must rearrange its characters so that no two adjacent characters are the same. If such an arrangement is impossible, return an empty string. The core challenge is distributing high-frequency characters so they never appear next to each other.

Approach 1: Greedy Heap Approach (O(n log k) time, O(k) space)

This method uses a heap (priority queue) to always pick the two characters with the highest remaining frequency. First count character frequencies using a hash table. Push each character and its count into a max heap. Repeatedly pop the top two characters, append them to the result, decrease their counts, and push them back if they still have remaining occurrences. Because the two most frequent characters are placed apart each step, adjacent duplicates never occur. The heap ensures we always use the most constrained characters first, which prevents situations where a high-frequency character gets stuck at the end. This approach works well when you want a straightforward greedy solution and is commonly used in interview explanations.

Approach 2: Counting and Greedy Placement (O(n) time, O(k) space)

This optimized approach relies on frequency counting and careful placement instead of a heap. Count occurrences of each character, then sort or identify the character with the highest frequency. Place this character at even indices (0, 2, 4, ...) of the result array first. After its occurrences are exhausted, fill the remaining positions with the other characters. The key insight is that spreading the most frequent character across even positions guarantees separation as long as its count does not exceed (n + 1) / 2. If it does, no valid arrangement exists. This technique leverages greedy placement and simple counting, reducing the complexity from heap operations to linear iteration. Many competitive programmers prefer this method because it achieves O(n) time with minimal overhead.

Recommended for interviews: The greedy heap solution is the most intuitive explanation during interviews because it clearly shows how you prioritize the most frequent characters and maintain separation. The counting-based greedy placement demonstrates deeper optimization and achieves linear time. Showing the heap approach first and then mentioning the O(n) counting optimization signals strong algorithmic reasoning.