A15097 | $Black and White Stripe$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

You have a stripe of checkered paper of length $n$ . Each cell is either white or black. What is the minimum number of cells that must be recolored from white to black in order to have a segment of $k$ consecutive black cells on the stripe? If the input data is such that a segment of $k$ consecutive black cells already exists, then print 0.

The first line contains an integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases. Next, descriptions of $t$ test cases follow. The first line of the input contains two integers $n$ and $k$ ( $1 \le k \le n \le 2\cdot10^5$ ). The second line consists of the letters 'W' (white) and 'B' (black). The line length is $n$ . It is guaranteed that the sum of values $n$ does not exceed $2\cdot10^5$ .

For each of $t$ test cases print an integer — the minimum number of cells that need to be repainted from white to black in order to have a segment of $k$ consecutive black cells.

输入 #1

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

输出 #1

C++ 编辑器

输入

输出