Rearrange a string so that no two adjacent characters are the same, with at least distance k apart.
Given a string s and an integer k, rearrange the string so that no two identical characters are adjacent, and characters of the same type are at least k positions apart. Return the rearranged string, or an empty string if not possible.
Examples
Input:["aabbcc",3]
Output:"abcabc"
Input:["aaabc",3]
Output:""
Hints
Use a max-heap to always pick the most frequent character.
Use a queue to keep track of characters that were recently used.
Only add characters back to the heap when they've had k distance.