CF1105B Zuhair and Strings

给定一个长度为 $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 翻译