hardHeap / Priority QueuePure DSA~45 min
Reorder Tasks So Identical Ones Are K Apart
A job runner must emit a sequence of task types such that any two runs of the same type are separated by at least k other tasks (to respect a per-type cooldown). Produce any valid ordering, or report that none exists.
Problem
Given a string s of task labels and an integer k, rearrange the characters so identical characters are at least k apart. Return any valid rearrangement, or an empty string if impossible.
Input
A string s and an integer k.
Output
A valid rearranged string, or an empty string.
Constraints
- 1 ≤ |s| ≤ 3e5
- 0 ≤ k ≤ |s|
- Lowercase English letters.
Examples
Example 1
Input
s="aabbcc" k=3
Output
abcabc
Each letter's repeats are 3 apart.
Example 2
Input
s="aaabc" k=3
Output
'a' appears 3 times but cannot be spaced 3 apart in length 5.