← 返回题目列表

Codeforces · 1690/D

D. 黑白条纹

中文机器翻译题面 查看原题

你有一条长度为 $$$n$$$ 的方格纸条。每个单元格要么是白色的,要么是黑色的。

为了在条纹上有 $$$k$$$ 连续黑色单元段,必须从白色重新着色为黑色的单元格的最小数量是多少?

如果输入数据已经存在一段 $$$k$$$ 连续黑色单元格,则打印 0。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

接下来是 $$$t$$$ 测试用例的描述。

输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2\cdot10^5$$$)。第二行由字母“W”(白色)和“B”(黑色)组成。线路长度为$$$n$$$。

保证 $$$n$$$ 值的总和不超过 $$$2\cdot10^5$$$。

输出

对于每个 $$$t$$$ 测试用例,打印一个整数 - 需要从白色重新绘制为黑色才能获得一段 $$$k$$$ 连续黑色单元的最小单元数。

示例

输入 #1

4
5 3
BBWBW
5 5
BBWBW
5 1
BBWBW
1 1
W

输出 #1

1
2
0
1

注意

在第一个测试用例中,$$$s$$$="BBWBW" 和 $$$k=3$$$。重新着色 $$$s_3$$$ 并得到 $$$s$$$="BBBBW" 就足够了。该字符串包含长度为 $$$k=3$$$ 的段,由字母“B”组成。

在示例 $$$s$$$="BBWBW" 和 $$$k=5$$$ 的第二个测试用例中。重新着色 $$$s_3$$$ 和 $$$s_5$$$ 并得到 $$$s$$$="BBBBB" 就足够了。该字符串包含长度为 $$$k=5$$$ 的段,由字母“B”组成。

在示例 $$$s$$$="BBWBW" 和 $$$k=1$$$ 的第三个测试用例中。字符串 $$$s$$$ 已包含长度为 $$$k=1$$$ 且由字母“B”组成的段。