【普及】字符出现至少k次的子字符串

给你一个字符串 s 和一个整数 $k$，在 s 的所有子字符串中，请你统计并返回 至少有一个 字符 至少出现 $k$ 次的子字符串总数。

子字符串 是字符串中的一个 连续、 非空 的字符序列。

输入格式

第一行包含 $2$ 个整数 $n, k(2 \le n \le 10^5, 1 \le k \le n)$，表示字符串个的长度和次数限制 $k$

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

输出格式

输出 $1$ 行包含 $1$ 个数，表示答案

5 2
abacb

4

5 1
abcde

15

提示

【样例 1 解释】 符合条件的子字符串如下：

• aba，字符 a 出现 $2$ 次
• abac 字符 a 出现 $2$ 次
• abacb 字符 a 出现 $2$ 次
• bacb 字符 b 出现 $2$ 次

【样例 2 解释】

• 所有子字符串都有效，因为每个字符至少出现一次

【数据范围】

• $2 \le n \le 10^5$
• $1 \le k \le n$
• s 仅由小写英文字母组成

来源

• 参考答案