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 distance apart. In other words, if the maximum frequency of any character in s is \( \text{maxFreq} \), then a valid rearrangement exists only if \( (\text{maxFreq} - 1)\times k \leq |s| - \text{maxFreq} \). If such a rearrangement is possible, output one valid arrangement; otherwise, output an empty string.

Note: The rearranged string does not have to be unique. All input strings consist of lowercase English letters.

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 a positive integer k.

outputFormat

Output a single line to standard output (stdout) containing the rearranged string such that the same characters are at least k positions apart. If no valid rearrangement exists, output an empty string.

aabbcc
3

abcabc