Rearrange String k Distance Apart - Video Solutions
LeetCode 358. Rearrange String k Distance Apart Explanation and Solution
Rearrange String k Distance Apart - Video Solution
Watch 10 video solutions for Rearrange String k Distance Apart, a hard level problem involving Hash Table, String, Greedy. This walkthrough by happygirlzt has 3,710 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 * 105sconsists of only lowercase English letters.0 <= k <= s.length
Approach Overview
Problem 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.
Complexity Analysis
| 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 |