[Solution] K-Flip solution codechef

Table of Contents

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.

For Solution

“Click Here”

Leave a Comment