Rearrange String K Distance Apart

Given a string s and a positive integer k, rearrange the characters of s so that the same characters are at least k positions apart. If such an arrangement is not possible, return an empty string.

The challenge requires you to implement a greedy algorithm using a max-heap (or priority queue) to always choose the character with the highest available frequency while ensuring that characters that were recently used are kept waiting until they can be reused.

The rearranged string must have the property that for any two adjacent positions containing the same character, the distance between their indices is at least k. Otherwise, output an empty string.

Note: If k is less than or equal to 1, the original string is a valid output.

inputFormat

The input consists of a single line containing a string s and an integer k separated by whitespace. The string consists of lowercase English letters.

outputFormat

Output the rearranged string such that any two identical characters are at least k positions apart. If no valid rearrangement exists, output an empty string.## sample

aabbcc 3

abcabc