Problem Description

Given a string \( s \) consisting only of lowercase English letters.

In each operation, you can choose any character in \( s \) and modify it to any lowercase English letter.

You can perform these operations in any order, but no more than \( k \) times, to minimize the length of the strict periodic substring of \( s \). Of course, you can also choose not to perform any operations.

Please output the smallest possible length of the strict periodic substring of \( s \) after all operations.

A string \( t \) is called a strict periodic substring of \( s \) if and only if \( s \) can be constructed by repeating \( t \) several times.

For example: mai is a strict periodic substring of maimai, dx is a strict periodic substring of dx. But ov is not a strict periodic substring 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

A single integer on one line, representing the answer.

Sample Input and Output

Sample Input #1

1
test

Sample Output #1

4

Sample Input #2

3
test

Sample Output #2

1

Sample Input #3

3
apollo

Sample Output #3

3

Notes

[Sample Explanation #1]

It can be proven that with at most one operation, the length of the strict periodic substring is at least 4.

[Sample Explanation #2]

By performing 3 operations, you can change test to ssss, making the length of the strict periodic substring 1.

[Data Range]

This problem uses batched testing.

• 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 restrictions.

For all test data, it is guaranteed that \( 0 \leq k < |s| \leq 10^6 \), and \( s \) contains only lowercase English letters.

July 28, 2024: Added a new Hack data set.

见题面 Input 部分

见题面 Output 部分