Black and White Stripe (Codeforces 1690D)
Tags: Implement, two pointers

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. 

Input: 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$$$.

Output: 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.

Note: 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'.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'.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'.

Sample Inputs:
4
5 3
BBWBW
5 5
BBWBW
5 1
BBWBW
1 1
W

Sample Outputs:
1
2
0
1

Solution (Python):
class Solution:

    def __init__(self):
        pass

    def solve(self):
        t = int(input())
        result = []
        for i in range(t):
            (n, k) = map(int, input().split())
            s = input()
            count = 0
            for j in range(k):
                if s[j] == 'W':
                    count += 1
            repaint = count
            for j in range(k, n):
                if s[j] == 'W':
                    count += 1
                if s[j - k] == 'W':
                    count -= 1
                repaint = min(repaint, count)
            result.append(repaint)
        for x in result:
            print(x)
if __name__ == '__main__':
    sol = Solution()
    sol.solve()

Solution (Python):
from sys import stdin, stdout

def howmany(n, k, stripes):
    rb = sum([1 for s in stripes[:k] if s == 'B'])
    mb = rb
    for i in range(0, n - k):
        if mb == k:
            return 0
        if stripes[i] == 'B':
            rb -= 1
        if stripes[k + i] == 'B':
            rb += 1
        if rb > mb:
            mb = rb
    return k - mb

def main():
    ncases = int(stdin.readline())
    for t in range(ncases):
        if t > 0:
            stdout.write('\n')
        [n, k] = [int(i) for i in stdin.readline().strip().split(' ')]
        stripes = stdin.readline().strip()
        stdout.write(str(howmany(n, k, stripes)))
if __name__ == '__main__':
    main()

Solution (Python):
def A(x, y):
    for i in range(x):
        (m, n) = map(int, y[2 * i])
        z = y[2 * i + 1].strip()
        prefix_sum = [0] * (m + 1)
        for j in range(1, m + 1):
            prefix_sum[j] = prefix_sum[j - 1] + (z[j - 1] == 'W')
        min_count = float('inf')
        for j in range(m - n + 1):
            count = prefix_sum[j + n] - prefix_sum[j]
            min_count = min(min_count, count)
        print(min_count)
x = int(input())
count = []
for _ in range(x):
    y = input().split()
    z = input()
    count.append(y)
    count.append(z)
A(x, count)