K-beautiful Strings
Contest: Codeforces Round 705 (Div. 2)
Difficulty rating: 2000
Tags: binary search, brute force, constructive algorithms, greedy, strings

You are given a string $$$s$$$ consisting of lowercase English letters and a number $$$k$$$. Let's call a string consisting of lowercase English letters beautiful if the number of occurrences of each letter in that string is divisible by $$$k$$$. You are asked to find the lexicographically smallest beautiful string of length $$$n$$$, which is lexicographically greater or equal to string $$$s$$$. If such a string does not exist, output $$$-1$$$.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

Input format:
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10\,000$$$) — the number of test cases.

The next $$$2 \cdot T$$$ lines contain the description of test cases. The description of each test case consists of two lines.

The first line of the description contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^5$$$) — the length of string $$$s$$$ and number $$$k$$$ respectively.

The second line contains string $$$s$$$ consisting of lowercase English letters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case output in a separate line lexicographically smallest beautiful string of length $$$n$$$, which is greater or equal to string $$$s$$$, or $$$-1$$$ if such a string does not exist.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case "acac" is greater than or equal to $$$s$$$, and each letter appears $$$2$$$ or $$$0$$$ times in it, so it is beautiful.

In the second test case each letter appears $$$0$$$ or $$$1$$$ times in $$$s$$$, so $$$s$$$ itself is the answer.

We can show that there is no suitable string in the third test case.

In the fourth test case each letter appears $$$0$$$, $$$3$$$, or $$$6$$$ times in "abaabaaab". All these integers are divisible by $$$3$$$.

Example input:
4
4 2
abcd
3 1
abc
4 3
aaaa
9 3
abaabaaaa

Example output:
acac
abc
-1
abaabaaab

Editorial:
First of all, let's notice that if the length of the string $$$n$$$ is not divisible by $$$k$$$, no beautiful string of such length exists. Otherwise the answer to the problem always exists (because the string $$$zz \ldots z$$$ is the greatest string of length $$$n$$$ and is beautiful).
If the string $$$s$$$ is beautiful, then $$$s$$$ itself is the answer. Otherwise, let's iterate over all the options of the maximal common prefix of the answer string and $$$s$$$, that way we will iterate from $$$n-1$$$ to $$$0$$$.
Let's maintain an array $$$cnt_i$$$ — how many times does the $$$i$$$-th leter of English alphabet occur in the prefix we have fixed. We can recalculate that array totally in $$$0(n)$$$, because when we iterate to the smaller prefix we only need to change one value of $$$cnt$$$.
Denote the length of common prefix as $$$pref$$$. Let's iterate over all possible letters at position $$$pref+1$$$ (numeration starts from one) in increasing order. We need to iterate over all letters that are strictly greater than $$$s_{pref+1}$$$, because otherwise either the answer will be less than $$$s$$$ or the length of common prefix won't be equal to $$$pref$$$.
Now we need to learn how to check quickly if we can pick any suffix so that we will get a beautiful string. To do that you need to go through the array $$$cnt$$$ and to calculate for each letter which miminal number of times we need to write it more in order to get the amount of occurences divisible by $$$k$$$. For $$$i$$$-th leter it is $$$(k-cnt_i$$$ $$$\%$$$ $$$k)$$$ $$$\%$$$ $$$k$$$. Let $$$sum$$$ be the sum of such value over all $$$i$$$. If $$$sum$$$ isn't greater than the length of the suffix, then what's left is to find the minimal suffix.
How to build the minimal suffix: let's denote the length of unknown suffix as $$$suff$$$ ($$$suff=n-pref-1$$$). We know that $$$sum \le suff$$$. If $$$sum < suff$$$, then let's increase the amount of occurences of $$$a$$$ on suffix by $$$suff-sum$$$. Now we will place all letters $$$a$$$, then all letters $$$b$$$ and so on to $$$z$$$.
A detail of realization: we will consider iterated letter at position $$$pref+1$$$ in the array $$$cnt$$$. We can maintain array $$$cnt$$$ on prefix of length $$$pref+1$$$ and take into account that $$$pref+1$$$-st symbol is the iterated symbol and not the symbol of string $$$s$$$.
The complexity of solution is $$$O(n \cdot C)$$$, where $$$C$$$ is the size of the alphabet ($$$26$$$). You can also write a solution in $$$O(n)$$$, by maintaining the sum $$$(k-cnt_i$$$ $$$\%$$$ $$$k)$$$ $$$\%$$$ $$$k$$$ in a variable.