K-beautiful 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≠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

The first line contains a single integer T (1≤T≤10000) — the number of test cases.   The next 2⋅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≤k≤n≤105) — 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 105.

Output

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.  

解题思路

思路来源赛后的题解，姑且用注释标注了一下自己的理解

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int cnt[30];
 4 int get(int x, int k) { return (k - x % k) % k; }    //当一个字母的当前数量为x时，还需要多少个该字母才能满足要求
 5 void solve()
 6 {
 7     int k, n;
 8     cin >> n >> k;
 9     string s;
10     cin >> s;
11     if (n % k != 0)        //如果字符串的长度不能被k整除，那么必定无解
12     {
13         cout << "-1\n";
14         return;
15     }
16     int sum = 0;    //每个字母的总需求
17     int flag = 1;    //判断是否继续寻找的标志
18     for (int i = 0; i < 30; i++)    //初始化
19     {
20         cnt[i] = 0;
21     }
22     for (auto c : s)    //统计每个字母出现次数
23     {
24         cnt[c - 'a']++;
25     }
26     for (int i = 0; i < 26; i++)    //统计初始条件下的sum
27     {
28         sum += get(cnt[i], k);
29     }
30     if (sum == 0)    //如果初始条件下就不需要改变任意一个字母，说明原字符串符合，直接输出
31     {
32         cout << s << "\n"; 
33         flag = 0;    //更改标志，跳过查找
34     }
35     for (int i = n - 1; i >= 0 && flag; i--)    //从后到前的一个贪心查找，直到找到为止
36     {
37         sum -= get(cnt[s[i] - 'a'], k);            //更新sum值，相当于在字符串中将当前位置的字母去除
38         cnt[s[i] - 'a']--;                        //
39         sum += get(cnt[s[i] - 'a'], k);            //
40         for (int j = s[i] - 'a' + 1; j < 26; j++)    //寻找当前字母的替代字母，从下一个字母到z
41         {
42             int lsum = sum;                //记录更改前的sum，用于还原
43             sum -= get(cnt[j], k);        //假设当前字母为j
44             cnt[j]++;                    //
45             sum += get(cnt[j], k);        //
46 
47             if (i + 1 + sum <= n)                //如果从当前位置到串尾的长度大于等于sum，即需要的sum的值可以得到满足，说明这种情况下可以满足条件
48             {
49                 for (int k = 0; k < i; k++)        //i之前的字符没有改变，直接输出
50                 {
51                     cout << s[k];
52                 }
53                 cout << char(j + 'a');            //当前字符
54                 string add = "";
55                 for (int w = 0; w < 26; w++)
56                 {
57                     int f = get(cnt[w], k);        //把每种字母需要的数量都填入add
58                     while (f)
59                     {
60                         f--;
61                         add += char(w + 'a');
62                     }
63                 }
64                 while ((int)add.size() + i + 1 < n)        //多余的空位用a补全，因为总长和其余每种字符数量都可以被k整除，所以填入a后a的数量也满足要求
65                     add += "a";
66                 sort(add.begin(), add.end());            //排序，把a挪到前面，实现最小字符串
67                 cout << add << "\n";
68                 flag = 0;                                //更改flag，跳过剩余循环
69                 break;
70             }
71             cnt[j]--;                //还原情况，进行下一次查找
72             sum = lsum;
73         }
74     }
75 }   
76 int main()
77 {
78     ios::sync_with_stdio(false);
79     cin.tie(0);
80     int t;
81     cin >> t;
82     while (t--)
83     {
84         solve();
85     }
86     return 0;
87 }