Balanced Suffix CodeChef Solution

Problem

You’re given a string $S$ of length $N$ and an integer $K$.

Let $C$ denote the set of all characters in $S$. The string $S$ is called good if, for every suffix of S:

• The difference between the frequencies of any two characters in $C$ does not exceed $K$.
  In particular, if the set $C$ has a single element, the string $S$ is good.

Find whether there exists a rearrangement of $S$ which is good.
If multiple such rearrangements exist, print the lexicographically smallest rearrangement.
If no such rearrangement exists, print $-1$ instead.

Note that a suffix of a string is obtained by deleting some (possibly zero) characters from the beginning of the string. For example, the suffixes of $S=abca$ are $\{a,ca,bca,abca\}$.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• Each test case consists of two lines of input.
  • The first line of each test case contains two space-separated integers $N$ and $K$ — the length of the string and the positive integer as mentioned in the statement, respectively.
  • The next line consists of a string $S$ of length $N$ containing lowercase English alphabets only.

Output Format

For each test case, output on a new line the lexicographically smallest good rearrangement of $S$.

If no such rearrangement exists, print $-1$ instead.

Constraints

Sample 1:

4
3 1
aaa
4 2
baba
4 1
babb
7 2
abcbcac

aaa
aabb
-1
abcabcc

Explanation:

Test case $1$: Since $C=\{a\}$, the string $S$ is good.

Test case $2$: The set $C=\{a,b\}$. Consider the rearrangement $aabb$. Let ��fa​ and ��fb​ denote the frequencies of $a$ and $b$ respectively:

• In suffix $b$, ��=1fb​=1 and ��=0fa​=0. Thus, ∣��−��∣=1≤�∣fb​−fa​∣=1≤K.
• In suffix $bb$, ��=2fb​=2 and ��=0fa​=0. Thus, ∣��−��∣=2≤�∣fb​−fa​∣=2≤K.
• In suffix $abb$, ��=2fb​=2 and ��=1fa​=1. Thus, ∣��−��∣=1≤�∣fb​−fa​∣=1≤K.
• In suffix $aabb$, ��=2fb​=2 and ��=2fa​=2. Thus, ∣��−��∣=0≤�∣fb​−fa​∣=0≤K.

Thus, the rearrangement $aabb$ is good. It is also the lexicographically smallest rearrangement possible of string $S$.

Test case $3$: It can be proven that there exists no rearrangement of $S$ which is good.

Test case $4$: The set $C=\{a,b,c\}$. Consider the rearrangement $abcabcc$. Let ��,��,fa​,fb​, and ��fc​ denote the frequencies of $a,b,$ and $c$ respectively:

• In suffix $c$, ��=0,��=0,fa​=0,fb​=0, and ��=1fc​=1. Thus, ∣��−��∣,∣��−��∣,∣fb​−fa​∣,∣fc​−fb​∣, and ∣��−��∣∣fa​−fc​∣ are all less than or equal to $K=2$.
• In suffix $cc$, ��=0,��=0,fa​=0,fb​=0, and ��=2fc​=2. Thus, ∣��−��∣,∣��−��∣,∣fb​−fa​∣,∣fc​−fb​∣, and ∣��−��∣∣fa​−fc​∣ are all less than or equal to $K=2$.
• In suffix $bcc$, ��=0,��=1,fa​=0,fb​=1, and ��=2fc​=2. Thus, ∣��−��∣,∣��−��∣,∣fb​−fa​∣,∣fc​−fb​∣, and ∣��−��∣∣fa​−fc​∣ are all less than or equal to $K=2$.
• In suffix $abcc$, ��=1,��=1,fa​=1,fb​=1, and ��=2fc​=2. Thus, ∣��−��∣,∣��−��∣,∣fb​−fa​∣,∣fc​−fb​∣, and ∣��−��∣∣fa​−fc​∣ are all less than or equal to $K=2$.
• In suffix $cabcc$, ��=1,��=1,fa​=1,fb​=1, and ��=3fc​=3. Thus, ∣��−��∣,∣��−��∣,∣fb​−fa​∣,∣fc​−fb​∣, and ∣��−��∣∣fa​−fc​∣ are all less than or equal to $K=2$.
• In suffix $bcabcc$, ��=1,��=2,fa​=1,fb​=2, and ��=3fc​=3. Thus, ∣��−��∣,∣��−��∣,∣fb​−fa​∣,∣fc​−fb​∣, and ∣��−��∣∣fa​−fc​∣ are all less than or equal to $K=2$.
• In suffix $abcabcc$, ��=2,��=2,fa​=2,fb​=2, and ��=3fc​=3. Thus, ∣��−��∣,∣��−��∣,∣fb​−fa​∣,∣fc​−fb​∣, and ∣��−��∣∣fa​−fc​∣ are all less than or equal to $K=2$.

Thus, the rearrangement $abcabcc$ is good. It is also the lexicographically smallest good rearrangement of string $S$.