← 返回题目列表

Codeforces · 1105/B

B. Zuhair 和弦乐

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的字符串 $$$s$$$ 和整数 $$$k$$$ ($$$1 \le k \le n$$$)。字符串$$$s$$$有一个级别$$$x$$$,如果$$$x$$$是最大的非负整数,这样就可以在$$$s$$$中找到:

- $$$x$$$ 长度为 $$$k$$$ 的非相交(非重叠)子串,
- 这些 $$$x$$$ 子字符串的所有字符都是相同的(即每个子字符串仅包含一个不同的字符,并且该字符对于所有子字符串都是相同的)。

子字符串是连续(相邻)字符的序列,它由两个整数 $$$i$$$ 和 $$$j$$$ 定义($$$1 \le i \le j \le n$$$),表示为 $$$s[i \dots j]$$$ = "$$$s_{i}s_{i+1} \dots s_{j}$$$"。

例如,如果 $$$k = 2$$$,则:

- 字符串“aabb”的级别为$$$1$$$(您可以选择子字符串“aa”),
- 字符串“zzzz”和“zzbzz”的级别为$$$2$$$(您可以在每个字符串中选择两个不相交的子字符串“zz”),
- 字符串“abed”和“aca”的级别为$$$0$$$(您无法找到至少一个长度为$$$k=2$$$且包含唯一不同字符的子字符串)。

Zuhair 为您提供了整数 $$$k$$$ 和长度为 $$$n$$$ 的字符串 $$$s$$$。您需要找到 $$$x$$$,即字符串 $$$s$$$ 的级别。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) - 字符串的长度和 $$$k$$$ 的值。

第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$,仅由小写拉丁字母组成。

输出

打印单个整数 $$$x$$$ — 字符串的级别。

示例

输入 #1

8 2
aaacaabb

输出 #1

2

输入 #2

2 1
ab

输出 #2

1

输入 #3

4 2
abab

输出 #3

0

注意

在第一个示例中,我们可以选择$$$2$$$由字母'a'组成的不相交子串:“(aa)ac(aa)bb”,因此级别为$$$2$$$。

在第二个示例中,我们可以选择子字符串“a”或“b”来获得答案$$$1$$$。