题目描述

对于由小写英文字母组成的字符串 $T$，我们定义如下问题，并将其答案记为 $f(T)$。

请计算通过任意次数地将 $T$ 的首字母删除并添加到末尾所能得到的不同字符串的种类数。

现给定一个长度为 $N$ 的小写英文字母字符串 $S$。你可以进行不超过 $K$ 次如下操作（也可以一次都不操作）：

• 选择 $S$ 中的任意一个字符，并将其更改为任意小写英文字母。

请你求出经过操作后，$f(S)$ 可能取得的最小值。

输入格式

输入通过标准输入按以下格式给出。

$N$ $K$ $S$

输出格式

请输出答案。

样例 1

输入

4 1
abac

输出

2

样例 2

输入

10 0
aaaaaaaaaa

输出

1

样例 3

输入

6 1
abcaba

输出

3

说明/提示

限制条件

• $1 \leq N \leq 2000$
• $0 \leq K \leq N$
• $S$ 是由小写英文字母组成的长度为 $N$ 的字符串。
• $N,K$ 均为整数。

样例解释 1

在第 $1$ 次操作时，将第 $4$ 个字符从 c 改为 b，此时 $S = abab$，$f(S) = 2$。无法通过 $1$ 次及以下的操作使 $f(S)$ 降到 $1$ 或更低，因此答案为 $2$。

由 ChatGPT 4.1 翻译