Given a string s and an integer k, rearrange s such that the same characters are at least distance k from each other. If it is not possible to rearrange the string, return an empty string "".
Example 1:
Input: s = "aabbcc", k = 3 Output: "abcabc" Explanation: The same letters are at least a distance of 3 from each other.
Example 2:
Input: s = "aaabc", k = 3 Output: "" Explanation: It is not possible to rearrange the string.
Example 3:
Input: s = "aaadbbcc", k = 2 Output: "abacabcd" Explanation: The same letters are at least a distance of 2 from each other.
Constraints:
1 <= s.length <= 3 * 105s consists of only lowercase English letters.0 <= k <= s.lengthProblem Overview: You are given a string s and an integer k. Rearrange the characters so that the same characters appear at least k distance apart. If such an arrangement is impossible, return an empty string. The challenge is balancing character frequency while respecting the spacing constraint.
Approach 1: Greedy Placement with Sorting (O(n^2) time, O(n) space)
Count the frequency of each character using a hash table. Repeatedly pick the character with the highest remaining frequency that does not violate the k-distance rule. Each placement requires scanning previously used characters or maintaining a temporary blocked set until the cooldown expires. Because the algorithm repeatedly searches for the next valid character, the selection step can degrade to O(n) per placement, leading to O(n^2) time. This approach demonstrates the greedy idea but becomes inefficient for large inputs.
Approach 2: Greedy + Max Heap + Cooldown Queue (O(n log σ) time, O(σ) space)
The optimal strategy uses a max heap (priority queue) to always place the character with the highest remaining frequency. First compute frequencies with a hash map. Push characters into a max heap ordered by remaining count. Each step pops the most frequent character, appends it to the result, and decreases its count.
To enforce the k spacing rule, push the used character into a cooldown queue with the index when it can be used again (current_index + k). While building the string, check the queue front; once its cooldown expires, push that character back into the heap. This guarantees that a character cannot reappear before k positions pass.
The greedy insight: always place the most frequent available character. High-frequency characters are the hardest to distribute; scheduling them early avoids dead ends later. Heap operations cost O(log σ) where σ is the number of unique characters, so building the result takes O(n log σ) time.
Recommended for interviews: Interviewers typically expect the greedy heap solution. A brute-force greedy attempt shows you understand the spacing constraint, but the max heap with cooldown queue demonstrates mastery of greedy scheduling and priority queues. It cleanly enforces the distance rule while always choosing the best next character.
We use a hash table or array cnt to count the occurrences of each character in the string. Then, we use a max heap pq to store each character and its count. Each element in the heap is a tuple (v, c), where v is the count and c is the character.
When rearranging the string, we repeatedly pop the top element (v, c) from the heap, add character c to the result string, and push (v-1, c) into a queue q. When the length of the queue q reaches k or more, we pop the front element; if its v is greater than 0, we push it back into the heap. Repeat this process until the heap is empty.
Finally, we check whether the length of the result string equals the original string. If so, we return the result string; otherwise, we return an empty string.
The time complexity is O(n log n), where n is the length of the string. The space complexity is O(|\Sigma|), where |\Sigma| is the size of the character set, which is 26 in this problem.
Related problems:
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Placement with Repeated Scanning | O(n^2) | O(n) | Useful for understanding the constraint and basic greedy idea, but inefficient for large inputs |
| Greedy + Max Heap + Cooldown Queue | O(n log σ) | O(σ) | General optimal solution when characters have different frequencies and spacing constraints must be enforced |
Reorganize String - Tesla Interview Question - Leetcode 767 - Python • NeetCode • 57,555 views views
Watch 9 more video solutions →Practice Rearrange String k Distance Apart with our built-in code editor and test cases.
Practice on FleetCode