/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
英小文字からなる文字列 T に対して次の問題を考え、その答えを f(T) とします。
T の先頭の文字を削除し末尾に追加する操作を任意の回数行うことによって作ることのできる文字列の種類数を求めてください。
英小文字からなる長さ N の文字列 S が与えられます。あなたは以下の操作を K 回以下行うことが出来ます。(1 回も行わなくてもよいです。)
- S の文字を 1 個選び、任意の英小文字に変更する。
操作終了後の f(S) の値としてあり得る最小値を求めてください。
制約
- 1 \le N \le 2000
- 0 \le K \le N
- S は英小文字からなる長さ N の文字列である。
- N,K は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N K S
出力
答えを出力せよ。
入力例 1
4 1 abac
出力例 1
2
1 回目の操作で 4 文字目を c から b に変更すると S= abab となり、f(S)=2 となります。
f(S) を 1 回以下の操作で 1 以下にすることはできないため、答えは 2 です。
入力例 2
10 0 aaaaaaaaaa
出力例 2
1
入力例 3
6 1 abcaba
出力例 3
3
Score : 300 points
Problem Statement
For a string T consisting of lowercase English letters, consider the question below, and let f(T) be the answer.
Find the number of different strings obtained by performing the following operation any number of times: delete the first character from T and append it to the end.
You are given a string S of length N consisting of lowercase English letters. You can perform the operation below at most K times (possibly zero).
- Choose a character of S and change it to any lowercase English letter.
Find the minimum possible value of f(S) after your operations.
Constraints
- 1 \le N \le 2000
- 0 \le K \le N
- S is a string of length N consisting of lowercase English letters.
- N and K are integers.
Input
Input is given from Standard Input in the following format:
N K S
Output
Print the answer.
Sample Input 1
4 1 abac
Sample Output 1
2
If you change the fourth character c to b in the first operation, you get S= abab, with f(S)=2.
f(S) cannot be made 1 or less in one or fewer operations, so the answer is 2.
Sample Input 2
10 0 aaaaaaaaaa
Sample Output 2
1
Sample Input 3
6 1 abcaba
Sample Output 3
3