[Solution] Split The String CodeChef Solution

Problem

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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

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

Is it hot or cold CodeChef Solution

Maximise the Tastiness CodeChef Solution

N Buttons 1 Bulb CodeChef Solution

Valid Minimum CodeChef Solution

High Frequency CodeChef Solution

Split The String CodeChef Solution

Monks CodeChef Solution

Good Indices CodeChef Solution

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.

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.