1690D.md (1779B)
1 Source: https://codeforces.com/problemset/problem/1690/D 2 3 D. Black and White Stripe 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You have a stripe of checkered paper of length $n$. Each cell is either white or black. 22 23 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? 24 25 If the input data is such that a segment of $k$ consecutive black cells already exists, then print 0. 26 27 Input 28 29 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 30 31 Next, descriptions of $t$ test cases follow. 32 33 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$. 34 35 It is guaranteed that the sum of values $n$ does not exceed $2\cdot10^5$. 36 37 Output 38 39 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. 40 41 Example 42 43 Input 44 45 ``` 46 4 47 48 5 3 49 50 BBWBW 51 52 5 5 53 54 BBWBW 55 56 5 1 57 58 BBWBW 59 60 1 1 61 62 W 63 ``` 64 65 Output 66 67 ``` 68 1 69 2 70 0 71 1 72 ``` 73 74 Note 75 76 In the first test case, $s$="BBWBW" and $k=3$. It is enough to recolor $s_3$ and get $s$="BBBBW". This string contains a segment of length $k=3$ consisting of the letters 'B'. 77 78 In the second test case of the example $s$="BBWBW" and $k=5$. It is enough to recolor $s_3$ and $s_5$ and get $s$="BBBBB". This string contains a segment of length $k=5$ consisting of the letters 'B'. 79 80 In the third test case of the example $s$="BBWBW" and $k=1$. The string $s$ already contains a segment of length $k=1$ consisting of the letters 'B'.