题目描述

给定一个长度为 $n$ 的字符串 $s$ 和一个整数 $k$（$1 \le k \le n$）。如果存在最大的非负整数 $x$，使得在 $s$ 中可以找到：

• $x$ 个互不相交（不重叠）的长度为 $k$ 的子串，
• 这 $x$ 个子串中的所有字符都相同（即每个子串只包含一种字符，并且所有子串的字符都相同），

那么称字符串 $s$ 的等级为 $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$，你需要求出字符串 $s$ 的等级 $x$。

输入格式

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

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

输出格式

输出一个整数 $x$，表示字符串的等级。

说明/提示

在第一个样例中，可以选取 $2$ 个由字母 'a' 组成的不重叠子串："(aa)ac(aa)bb"，所以等级为 $2$。

在第二个样例中，可以选取 "a" 或 "b" 作为子串，答案为 $1$。

由 ChatGPT 4.1 翻译

样例

8 2
aaacaabb

2

2 1
ab

1

4 2
abab

0