# [Solution] K-Flip solution codechef

## K-Flip solution codechef

K-Flip solution codechef – You are given a binary string S of length N. You are also given an integer K. You can do the following operation at most N-K+1 times:

• First, choose a substring of S of length exactly K. This substring shouldn’t have been chosen in any of the previous operations.
• Then, flip all the characters of the chosen substring (i.e. change every 0 to 1 and vice versa).

Find the lexicographically smallest string possible after the operations if you do them in an optimal way.

Note:

• A substring is consecutive elements of a string. For eg. in the string “01011”, “101” is a substring, but “111” is not a substring.
• A string A is lexicographically smaller than string B, if A_i \lt B_i, where i is the first index where A and B differ.

## [Solution] K-Flip solution codechef

• The first line of input will contain a single integer T, denoting the number of test cases.
• The first line of each test case contains two space-separated integers: NK.
• The second line of each test case contains the string S.

### Output Format

For each test case, output on a new line the lexicographically smallest string that you can achieve.

### Constraints

• 1 \leq T \leq 100
• 1 \leq N \leq 10^5
• 1 \leq K \leq N
• Each element of S is either 0 or 1
• The sum of N over all test cases won’t exceed 3 \times 10^5.

### Sample 1:

Input

Output

4
3 2
101
4 2
1011
5 3
01010
5 2
01010

000
0001
00011
00000


## [Solution] K-Flip solution codechef

### Explanation:

Test case 1: Choose the substring 1\textcolor{red}{01} and flip it. So now S becomes 110. Then choose the substring \textcolor{red}{11}0 and flip it. So now S becomes 000. This is the lexicographically smallest string that can be achieved, and hence this is the answer.

Test case 2: Choose the substring 1\textcolor{red}{01}1 and flip it. So now S becomes 1101. Then choose the substring \textcolor{red}{11}01 and flip it. So now S becomes 0001. This is the lexicographically smallest string that can be achieved, and hence this is the answer.

Test case 3: Choose the substring 0\textcolor{red}{101}0 and flip it. So now S becomes 00100. Then choose the substring 00\textcolor{red}{100} and flip it. So now S becomes 00011. This is the lexicographically smallest string that can be achieved, and hence this is the answer.

Test case 4: Choose the substring 01\textcolor{red}{01}0 and flip it. So now S becomes 01100. Then choose the substring 0\textcolor{red}{11}00 and flip it. So now S becomes 00000. This is the lexicographically smallest string that can be achieved, and hence this is the answer.