CF1105B.Zuhair and Strings

Given a string $s$ of length $n$ and integer $k$ ($1 \le k \le n$). The string $s$ has a level $x$, if $x$ is largest non-negative integer, such that it's possible to find in $s$:

• $x$ non-intersecting (non-overlapping) substrings of length $k$,
• all characters of these $x$ substrings are the same (i.e. each substring contains only one distinct character and this character is the same for all the substrings).

A substring is a sequence of consecutive (adjacent) characters, it is defined by two integers $i$ and $j$ ($1 \le i \le j \le n$), denoted as $s[i \dots j]$ = "$s_{i}s_{i+1} \dots s_{j}$".

For example, if $k = 2$, then:

• the string "aabb" has level $1$ (you can select substring "aa"),
• the strings "zzzz" and "zzbzz" has level $2$ (you can select two non-intersecting substrings "zz" in each of them),
• the strings "abed" and "aca" have level $0$ (you can't find at least one substring of the length $k=2$ containing the only distinct character).

Zuhair gave you the integer $k$ and the string $s$ of length $n$. You need to find $x$, the level of the string $s$.

给定一个长度为 $n$ 的字符串 $s$ 和一个整数 $k$（$1 \le k \le n$）。若 $x$ 是满足以下条件的最大非负整数，则称字符串 $s$ 的等级为 $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$ 且仅含一种字符的子串）。

祖海尔给了你整数 $k$ 和长度为 $n$ 的字符串 $s$。你需要求出 $s$ 的等级 $x$。

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the length of the string and the value of $k$.

The second line contains the string $s$ of length $n$ consisting only of lowercase Latin letters.

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

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

Print a single integer $x$ — the level of the string.

输出一个整数 $x$ —— 该字符串的等级。

In the first example, we can select $2$ non-intersecting substrings consisting of letter 'a': "(aa)ac(aa)bb", so the level is $2$.

In the second example, we can select either substring "a" or "b" to get the answer $1$.

在第一个例子中，我们可以选择 $2$ 个互不相交的、仅由字母 'a' 组成的子串："(aa)ac(aa)bb"，因此等级为 $2$。

在第二个例子中，我们可以选择子串 "a" 或 "b" 中的任意一个，从而得到答案 $1$。