【MX-S2-T1】变
题目描述
已知一个仅由小写英文字母构成的字符串 $s$。
每次操作时,你可以任意选择 $s$ 中的一个字符,并将它修改为任意小写英文字母。
你可以按任意顺序对其进行不超过 $k$ 次操作,以最小化 $s$ 的**严格循环节**的长度。当然,不进行操作也是可以的。
请输出在进行完所有操作后,最小的可能的 $s$ 的严格循环节的长度。
> 一个字符串 $t$ 被称为 $s$ 的严格循环节,当且仅当 $s$ 可以通过将 $t$ 重复若干次来构造。
>
> 例如:`mai` 是 `maimai` 的严格循环节,`dx` 是 `dx` 的严格循环节。但 `ov` 不是 `ovo` 的严格循环节。
输入输出格式
输入格式
第一行一个非负整数 $k$。
第二行一个字符串 $s$,仅包含小写英文字母。
输出格式
一行一个整数,表示答案。
输入输出样例
输入样例 #1
1
test
输出样例 #1
4
输入样例 #2
3
test
输出样例 #2
1
输入样例 #3
3
apollo
输出样例 #3
3
说明
**【样例解释 \#1】**
可以证明:最多进行一次操作的情况下,严格循环节长度至少为 $4$。
**【样例解释 \#2】**
可以通过 $3$ 次操作,将 `test` 修改为 `ssss`,严格循环节长度为 $1$。
**【数据范围】**
**本题采用捆绑测试。**
- Subtask 0(17 pts):$k = 0$,$|s| \leq 6$。
- Subtask 1(14 pts):$k = 1$,$|s| \leq 20$。
- Subtask 2(16 pts):$k = 1$,$|s| \leq 500$。
- Subtask 3(32 pts):$k < |s| \leq 10^5$。
- Subtask 4(21 pts): 无特殊限制。
对于所有测试数据,保证 $0 \leq k < |s| \leq 10^6$,$s$ 中仅包含小写英文字母。
**2024.7.28:新增了一组 Hack 数据。**