Rearrange String k Distance Apart

Given a string \( s \) and an integer \( k \), rearrange the string such that any two identical characters are at least \( k \) indices apart. If it is impossible to rearrange the string to meet this condition, output an empty string.

Example 1: For \( s = \texttt{aabbcc} \) and \( k = 3 \), one possible rearrangement is \( \texttt{abcabc} \).

Example 2: For \( s = \texttt{aaabc} \) and \( k = 3 \), no valid rearrangement exists, so the output is an empty string.

The challenge is to ensure that the rearranged string (if one exists) satisfies the condition that the distance between any two occurrences of the same character is at least \( k \). Use appropriate greedy and heap-based techniques to achieve this.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

• The first line contains the string \( s \) (a sequence of characters).
• The second line contains an integer \( k \).

outputFormat

The output is a single line printed to standard output (stdout) containing the rearranged string. If no valid rearrangement exists, output an empty string.

aabbcc
3

abcabc