[Solution] K-Flip CodeChef Solution | Solution CodeChef

Problem

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.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

• 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.

Input Format

• 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: $N$, $K$.
• 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.

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.