Rearrange String k Distance Apart - Solution & Explanation

Q: Is Rearrange String k Distance Apart easy or hard?

Rearrange String k Distance Apart is classified as a Hard problem because it combines greedy scheduling with heap management and constraint enforcement. The tricky part is ensuring characters re-enter the heap only after k positions have passed.

Q: Rearrange String k Distance Apart Python/Java solution

Most implementations follow the same structure across languages: count characters with a map, push them into a max heap ordered by frequency, then maintain a queue storing characters until their cooldown expires. Python uses heapq with negative counts, while Java uses PriorityQueue with a custom comparator.

Q: How to solve Rearrange String k Distance Apart in O(n)?

Strict O(n) is generally not achievable because the algorithm needs a priority structure to select the most frequent character. With a fixed alphabet (for example only lowercase letters), the heap size is bounded by 26, making the effective complexity close to O(n). In practice the max heap + cooldown queue solution behaves nearly linear.

Q: What is the best approach for Rearrange String k Distance Apart?

The most effective approach uses a greedy strategy with a max heap and a cooldown queue. A hash map counts character frequencies, the max heap always selects the most frequent available character, and the cooldown queue prevents reuse until k positions pass. This ensures valid spacing while keeping time complexity at O(n log σ), where σ is the number of distinct characters.

Q: Is Rearrange String k Distance Apart asked at Google/Amazon/Meta?

This problem appears in interview prep sets for companies like Google, Amazon, and Meta because it tests greedy reasoning and priority queue usage. Candidates must manage frequency counts and scheduling constraints simultaneously, which is a common systems-style allocation pattern.

Q: What data structure is used in Rearrange String k Distance Apart?

The core data structures are a hash table for counting frequencies, a max heap (priority queue) for selecting the next character with the highest remaining count, and a queue to track characters during their k-length cooldown window.

Q: What is the time complexity of Rearrange String k Distance Apart?

The optimal solution runs in O(n log σ) time and O(σ) space. Each character insertion and removal from the max heap costs O(log σ), and this happens once per character while constructing the result string.

HardPremiumFree on FleetCodeHash Table String Greedy Sorting10 min readAsked at: Amazon, Google, Tiktok +1

Practice this problem

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 * 10⁵
s consists 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.

Solution

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.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Detailed 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

Video Solution

LeetCode 358. Rearrange String k Distance Apart Explanation and Solution • happygirlzt • 3,710 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Rearrange String k Distance Apart easy or hard?

Rearrange String k Distance Apart is classified as a Hard problem because it combines greedy scheduling with heap management and constraint enforcement. The tricky part is ensuring characters re-enter the heap only after k positions have passed.

Rearrange String k Distance Apart Python/Java solution

Most implementations follow the same structure across languages: count characters with a map, push them into a max heap ordered by frequency, then maintain a queue storing characters until their cooldown expires. Python uses heapq with negative counts, while Java uses PriorityQueue with a custom comparator.

How to solve Rearrange String k Distance Apart in O(n)?

Strict O(n) is generally not achievable because the algorithm needs a priority structure to select the most frequent character. With a fixed alphabet (for example only lowercase letters), the heap size is bounded by 26, making the effective complexity close to O(n). In practice the max heap + cooldown queue solution behaves nearly linear.

What is the best approach for Rearrange String k Distance Apart?

The most effective approach uses a greedy strategy with a max heap and a cooldown queue. A hash map counts character frequencies, the max heap always selects the most frequent available character, and the cooldown queue prevents reuse until k positions pass. This ensures valid spacing while keeping time complexity at O(n log σ), where σ is the number of distinct characters.

Is Rearrange String k Distance Apart asked at Google/Amazon/Meta?

This problem appears in interview prep sets for companies like Google, Amazon, and Meta because it tests greedy reasoning and priority queue usage. Candidates must manage frequency counts and scheduling constraints simultaneously, which is a common systems-style allocation pattern.

What data structure is used in Rearrange String k Distance Apart?

The core data structures are a hash table for counting frequencies, a max heap (priority queue) for selecting the next character with the highest remaining count, and a queue to track characters during their k-length cooldown window.

What is the time complexity of Rearrange String k Distance Apart?

The optimal solution runs in O(n log σ) time and O(σ) space. Each character insertion and removal from the max heap costs O(log σ), and this happens once per character while constructing the result string.

Ready to solve this problem?

Practice Rearrange String k Distance Apart with our built-in code editor and test cases.

Practice on FleetCode

Construct String With Repeat Limit

Reorganize String

Problem Info

DifficultyHard

Acceptance39.9%

Approaches1

Reading time10 min

Asked at

Amazon Google Tiktok Zomato