Rearrange String with Distance Constraint

You are given a string \(s\) and an integer \(k\). The task is to rearrange the characters of \(s\) so that the same characters are at least \(k\) distance apart. If it is possible to obtain such an arrangement, output any valid rearranged string. Otherwise, output an empty string.

For example, if \(s = \texttt{aabbcc}\) and \(k = 3\), one possible rearrangement is \(\texttt{abcabc}\) because each occurrence of any character is spaced by at least 3 positions. However, if \(s = \texttt{aaabc}\) and \(k = 3\), it is impossible to rearrange the string to satisfy the condition, so the output should be empty.

Note: If \(k=0\), then no rearrangement is needed and the original string should be returned.

inputFormat

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

• The first line contains the string \(s\).
• The second line contains the integer \(k\).

outputFormat

Output to standard output (stdout) a single line containing the rearranged string if a valid arrangement exists. If no valid rearrangement exists, output an empty string.

aabbcc
3

abcabc