思路

设 $n=|s|$。
根据题目定义，严格循环节的长度必为 $n$ 的一个正因子。
通过查表可知，$n\le10^6$ 时 $\max \{ d(n) \} \le240$。
于是我们可以 $O \left( d(n) \right)$ 枚举严格循环节的长度，并 $O(n)$ 检验。
检验时，我们先将原字符串分成长度为 $i$ 的 $\frac{n}{i}$ 个字符串。对于第 $j\in [1,i]$ 位，这些字符串要全部修改为同一个字母。
显然每个第 $j$ 位互不影响。

我们假定要将这些字符串的第 $j$ 位修改成字母 $a$，那么除了本身第 $j$ 位就是 $a$ 的字符串无需修改以外，其他字符串都需要进行 $1$ 次修改。
我们要让修改次数尽可能小，就是要找到这些字符串第 $j$ 位上出现次数最多的字母，并将其他字符串第 $j$ 位修改成那个字母。
只需要对每个字符串第 $j$ 位遍历一遍即可。

复杂度

时间复杂度

$O(d(|s|)\times |s|)$

空间复杂度

$O(|s|)$

代码

#include<bits/stdc++.h>
using namespace std;
int k,l;
string s;
int cnt[26];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>k>>s;
	l=s.length();
	for(int i=1;i<=l;i++){
		if(l%i)continue;//不是因子，不处理
		bool f=1;
		int kk=k;
		for(int j=0;j<i;j++){
			int mx=0;
			memset(cnt,0,sizeof(cnt));
			for(int t=j;t<l;t+=i){
				int x=s[t]-'a';
				cnt[x]++;
				mx=max(cnt[x],mx);//统计出现次数最多的字母
			}
			kk-=(l/i-mx);//计算剩余修改次数
			if(kk<0){//修改次数不够，直接退出
				f=0;
				break;
			}
		}
		if(f){
			cout<<i;
			return 0;
		}
	}
	return 0;
}