Background

Original problem link: https://oier.team/problems/S2A。

Problem Description

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。

Input Format

The first line contains a non-negative integer $k$.

The second line contains a string $s$, consisting only of lowercase English letters.

Output Format

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

1
test

4

3
test

1

3
apollo

3

Hint

[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