# Split The String CodeChef Solution

### We Are Discuss About CODECHEF SOLUTION

Split The String CodeChef Solution

## Split The String CodeChef Solution

For a binary string A, let f(A) denote its badness, defined to be the difference between the number of zeros and number of ones present in it. That is, if the string has c_0 zeros and c_1 ones, its badness is |c_0 – c_1|. For example, the badness of “01” is |1 – 1| = 0, the badness of “100” is |2 – 1| = 1, the badness of “1101” is |1 – 3| = 2, and the badness of the empty string is |0 – 0| = 0.

You are given an integer N and a binary string S.

You would like to partition S into K disjoint subsequences (some of which may be empty), such that the maximum badness among all these K subsequences is minimized. Find this value.

Formally,

• Let S_1, S_2, \ldots, S_K be a partition of S into disjoint subsequences. Every character of S must appear in one of the S_i. Some of the S_i may be empty.
• Then, find the minimum value of \max(f(S_1), f(S_2), \ldots, f(S_K)) across all possible choices of S_1, S_2, \ldots, S_K satisfying the first condition.

### Input Format

• The first line of input will contain a single integer T, denoting the number of test cases.
• The description of each test case is as follows:
• The first line contains two space-separated integers N and K.
• The second line contains the binary string S of length N.

### Output Format

​For each test case, print the minimum possible value of the maximum badness when S is partitioned into K subsequences.

### Constraints

• 1 \leq T \leq 1000
• 1 \leq N \leq 2 \cdot 10^5
• 1 \leq K \leq 10^9
• S is a binary string, i.e, contains only the characters 0 and 1
• The sum of N across all test cases doesn’t exceed 2 \cdot 10^5

### Sample 1:

Input

Output

3
7 5
1010100
4 1
1100
6 2
101111
1
0
2

### Explanation:

Test case 1: Let’s take a couple of examples.

• Suppose the partition is \{“10”, “10”, “0”, “10”, “\ “\}, obtained as \textcolor{red}{10}\textcolor{blue}{10}\textcolor{orange}{10}0 (elements of one color form a subsequence). The respective badness values are \{0, 0, 1, 0, 0\}, the maximum of which is 1.
• Suppose the partition is \{“101”, “00”, “\ “, “10”, “\ “\}, obtained as \textcolor{red}{10}10\textcolor{red}{1}\textcolor{blue}{00}. The respective badness values are \{1, 2, 0, 0, 0\}, the maximum of which is 2.

The first partition, with a maximum badness of 1, is one of the optimal partitions.

Test case 2: The only possible partition is \{“1100″\}, which has a badness of 0.

Test case 3: The partitions \{“1011”, “11”\} and \{“0111”, “11”\} both lead to a badness of \max(2, 0) = 2, which is the minimum possible.

## SOLUTION

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here ScishowEngineer   Then Follow US HERE and Join Telegram.