题解

思路

一个长度为 $N$ 的字符串的不同循环移位数量，恰好等于它的最小周期长度，该周期一定整除 $N$。

做法

枚举一个约数 $d$ 作为目标周期后，所有下标对 $d$ 取模相同的位置必须改成同一个字符；对每个余数类统计 26 个字符的出现次数，保留出现最多的字符，其余位置都修改，就得到变成某个 $d$ 周期串所需的最少修改次数。

按 $d$ 从小到大枚举 $N$ 的约数，若各余数类的最少修改数之和不超过 $K$，就立即输出 $d$。即使得到的字符串还有更小周期，也只会使答案更小，而更小的约数已经先被检查，因此首个可行值就是答案。

复杂度

每个候选周期只需扫描字符串并统计频次，时间复杂度为 $O(N\tau(N)+26\sigma(N))$，在本题范围内可视为每个约数线性处理；空间复杂度为 $O(26N)$。