[R62D]好子串 - 代码源竞赛平台

时空限制

1s/512M

题目描述

给定一个长度为 $n$ 的字符串 $s$，该字符串中只包含大写字母 A、B、C。

对于 $s$ 的一个连续子串，如果可以通过修改其中至多 $k$ 个字符，使得该子串中的所有字符都相同，则称该子串是一个“好子串”。

请计算字符串 $s$ 中一共有多少个“好子串”。

注意：两个子串只要在 $s$ 中的起始位置或终止位置不同，就视作不同的子串（即使它们的内容完全相同）。

格式

输入格式

第一行包含两个整数 $n$ 和 $k$，分别表示字符串的长度和最大允许修改的字符数量。

第二行包含一个长度为 $n$ 且仅由 A、B、C 组成的字符串 $s$。

输出格式

输出一行一个整数，表示字符串 $s$ 中“好子串”的总数。

样例

样例输入 #1

5 1
ABCAB

样例输出 #1

9

数据规模

子任务编号	分数	$n\le$
$1$	$20$	$200$
$2$	$20$	$2000$
$3$	$60$	$2\times 10^5$

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$0 \le k \le n$，字符串 $s$ 仅包含大写字符 A、B、C。