K – balanced string solution codechef

K – balanced string solution codechef

A binary string SS of length NN is called KK-balanced string if it holds the following property: For each index i(1iN)i(1≤i≤N) such that Si=Si= ‘1’, there must exist an index j(1jN)j(1≤j≤N) such that Sj=Sj= ‘1’ and ij∣=K∣i−j∣=K, where x∣x∣ denotes the absolute value of xx.

For example, if K=1K=1, “00”, “110”, “011011” are 1-balanced strings, while “010” , “1001” are not; if K=2K=2, “10101”, “0101000101” are 2-balanced 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 KK-balanced?

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 space-separated 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 KK-balanced.

Constraints

  • 1T1051≤T≤105
  • 2N1052≤N≤105
  • 1KN1≤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 1-balanced string.

Test case 22: The given string is already 1-balanced.

Test case 33: Chef applies one operation on the index 33 and the string becomes “1111” which is a 2-balanced 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 3-balanced string.

Leave a Reply

Your email address will not be published. Required fields are marked *

*