P10810 [MX-S2-T1] Transform.

Original problem link: 。

You are given a string $s$ consisting only of lowercase English letters. In each operation, you may choose any character in $s$ and change it to any lowercase English letter. You may perform at most $k$ operations in any order to minimize the length of the **strict period** of $s$. Of course, you may also choose to perform no operations. Output the smallest possible length of the strict period of $s$ after all operations. > A string $t$ is called a strict period of $s$ if and only if $s$ can be constructed by repeating $t$ some number of times. > > For example, `mai` is a strict period of `maimai`, and `dx` is a strict period of `dx`. But `ov` is not a strict period of `ovo`。

The first line contains a non-negative integer $k$. The second line contains a string $s$, consisting only of lowercase English letters.

Output one integer on a single line, representing the answer.

**[Sample Explanation \#1]** It can be proven that with at most one operation, the strict period length is at least $4$. **[Sample Explanation \#2]** With $3$ operations, you can change `test` into `ssss`, and the strict period length is $1$. **[Constraints]** **This problem uses bundled testdata.** - 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): no special constraints. For all testdata, it is guaranteed that $0 \leq k < |s| \leq 10^6$, and $s$ contains only lowercase English letters. **2024.7.28: A new Hack testdata set has been added.** Translated by ChatGPT 5