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.

Description Solution Video 11:36

358. Rearrange String k Distance Apart

Hard39.9% acceptance4 companiesPremium elsewhere, free here

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

Asked at 4 companies

Zomato

Google Tiktok Amazon

Topics

11:36

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

358. Rearrange String k Distance Apart

Asked at 4 companies

Topics

Similar problems