Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.
Return any possible rearrangement of s or return "" if not possible.
Example 1:
Input: s = "aab" Output: "aba"
Example 2:
Input: s = "aaab" Output: ""
Constraints:
1 <= s.length <= 500s consists of lowercase English letters.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.
This approach utilizes a max heap to always place the character with the maximum frequency next, ensuring that no two adjacent characters are the same. If the character frequency is more than half of the string length, it is impossible to rearrange.
In this solution, we utilize Python's heapq library to simulate a max heap by storing negative frequencies. We arrange the highest frequency characters first and reinsert them with decremented counts after placing another character, ensuring no two adjacent characters are the same.
Time Complexity: O(n log k) where n is the length of the string and k is the number of unique characters. Space Complexity: O(n)
This approach utilizes a direct counting mechanism and attempts to place characters in a greedy manner, utilizing an array to keep track of placement positions for the most frequent characters first.
This C solution determines the most frequent character and places it in even indices. Other characters fill in remaining positions. If at any time the most frequent character cannot be placed, we return an empty string.
Time Complexity: O(n) due to linear scanning and filling. Space Complexity: O(1) since we use a fixed-size count array.
| Approach | Complexity |
|---|---|
| Greedy Heap Approach | Time Complexity: O(n log k) where n is the length of the string and k is the number of unique characters. Space Complexity: O(n) |
| Counting and Greedy Approach | Time Complexity: O(n) due to linear scanning and filling. Space Complexity: O(1) since we use a fixed-size count array. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Heap (Priority Queue) | O(n log k) | O(k) | General solution that works for any character distribution and is easy to reason about in interviews |
| Counting + Greedy Placement | O(n) | O(k) | Best when optimizing for linear time using frequency counting and index placement |
Reorganize String • Kevin Naughton Jr. • 79,250 views views
Watch 9 more video solutions →Practice Reorganize String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor