题目链接
解题思路
首先，如果原字符串是合法的直接输出原字符串即可。
然后我们考虑一个最简单的暴力，你枚举第一个你构造的字符串比原串大的字符的位置，再枚举这个字符，然后后面的肯定是从后往前贪心放即可，在此不再赘述。
这样的复杂度是 \(O(|S|^2 \times V^2)\) 的，其中 \(V = 26\)，\(|S|\) 代表给定的字符串长度，这样的时间复杂度并不优秀，不能通过本题，
考虑你从后缀往前扫，维护一个桶，每次向前一个字符只需要使用 \(O(1)\) 的时间复杂度修改，而从后缀往前扫，不难发现，这样构造出来的第一个字符串是一定最优的。
时间复杂度 \(O(|S| \times C^2)\)，可以通过此题。
参考代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
//#define map unordered_map
#define re register
#define ll long long
#define forl(i,a,b) for(re ll i=a;i<=b;i++)
#define forr(i,a,b) for(re ll i=a;i>=b;i--)
#define forll(i,a,b,c) for(re ll i=a;i<=b;i+=c)
#define forrr(i,a,b,c) for(re ll i=a;i>=b;i-=c)
#define pii pair<ll,ll>
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
#define pb push_back
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
ll _t_;
void _clear(){}
ll n,m;
string s;
ll a[30];
ll pd;
string ans;
ll f(char x){
return x-'a'+1;
}
void check(ll x,char y)
{
a[f(y)]++;
ll need=0;
// forl(i,1,10)
// cout<<a[i]<<' ';
// cout<<endl;
forl(i,1,26)
need+=(m-a[i]%m)%m;
// cout<<need<<' '<<n<<' '<<x<<endl;
if(n-x<need)
{
a[f(y)]--;
return ;
}
pd=1;
ans="";
forl(i,0,n)
ans+=' ';
forl(i,1,x-1)
ans[i]=s[i];
ans[x]=y;
ll id=0;
forr(i,n,x+1)
{
ll pd2=0;
forr(j,26,1)
if(a[j]%m)
{
a[j]++,ans[i]=j+'a'-1;
pd2=1;
break;
}
if(!pd2)
{
id=i;
break;
}
}
forl(i,x+1,id)
ans[i]='a';
}
void solve()
{
ans="",pd=0;
_clear();
cin>>n>>m>>s;
if(n%m)
{
cout<<-1<<endl;
return ;
}
s=' '+s;
forl(i,1,26)
a[i]=0;
forl(i,1,n)
a[f(s[i])]++;
forl(i,1,26)
{
if(a[i]%m)
break;
if(i==26)
{
for(auto j:s)
if(j!=' ')
cout<<j;
cout<<endl;
return ;
}
}
/** a[f(s[4])]--;
a[f(s[3])]--;
a[f(s[2])]--;
check(2,'c');*/
forr(i,n,1)
{
a[f(s[i])]--;
forl(j,s[i]+1,'z')
{
check(i,j);
if(pd)
{
for(auto j:ans)
if(j!=' ')
cout<<j;
cout<<endl;
return ;
}
}
}
}
int main()
{
IOS;
_t_=1;
cin>>_t_;
while(_t_--)
solve();
QwQ;
}