分数: 300 点
问题陈述
对于字符串 T 由小写英文字母组成,考虑下面的问题,令 f(T) 就是答案。
求执行任意次以下操作得到的不同字符串的数量:删除第一个字符 T 并将其附加到末尾。
给你一个字符串 S 长度 N 由小写英文字母组成。您最多可以执行以下操作 K 次(可能为零)。
- 选择一个字符 S 并将其更改为任意小写英文字母。
找到以下的最小可能值 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
如果更改第四个字符 c to b 在第一个操作中,您得到 S= abab,与 f(S)=2.
f(S) 无法制作 1 或更少的一次或更少的操作,所以答案是 2.
示例输入 2
10 0 aaaaaaaaaa
示例输出 2
1
示例输入 3
6 1 abcaba
示例输出 3
3