K – balanced string solution codechef

For Solution
Click Here!
A binary string SS of length NN is called KKbalanced string if it holds the following property: For each index i(1≤i≤N)i(1≤i≤N) such that Si=Si= ‘1’, there must exist an index j(1≤j≤N)j(1≤j≤N) such that Sj=Sj= ‘1’ and ∣i−j∣=K∣i−j∣=K, where ∣x∣∣x∣ denotes the absolute value of xx.
For example, if K=1K=1, “00”, “110”, “011011” are 1balanced strings, while “010” , “1001” are not; if K=2K=2, “10101”, “0101000101” are 2balanced strings, while “0110” , “1001”, “010” are not.
Chef is given a binary string SS of length NN and an integer KK. He can perform the following operation on the string:
 Select an index of the string, and flip the character at that index. This means if the character was “0”, it becomes “1”, and vice versa.
What is the minimum number of operations Chef will have to perform so that the string becomes KKbalanced?
K – balanced string solution codechef
 The first line of input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
 The first line of each test case contains two spaceseparated integers N,KN,K.
 The second line of each test case contains a string SS.
K – balanced string solution codechef
For each test case, print a single line containing one integer – the minimum number operation Chef needs to perform on the given string to make it KKbalanced.
Constraints
 1≤T≤1051≤T≤105
 2≤N≤1052≤N≤105
 1≤K≤N1≤K≤N
 SS contains only characters ‘00‘ and ‘11‘.
 The sum of NN over all test cases does not exceed 106106.
K – balanced string solution codechef
4
2 1
01
3 1
111
4 2
1101
5 3
11110
Sample Output 1
1
0
1
2
Explanation
Test case 11: Chef applies one operation on the index 22 and the string becomes “00” which is a 1balanced string.
Test case 22: The given string is already 1balanced.
Test case 33: Chef applies one operation on the index 33 and the string becomes “1111” which is a 2balanced string.
Test case 44: Chef applies one operation on the index 22 and another operation on the index 33. Hence, the string becomes “10010” which is a 3balanced string.

For Solution
Click Here!