Split The String 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.


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


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



7 5
4 1
6 2


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.


Split The String CodeChef Solution


Split The String CodeChef 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.

If You Want To Learn Something New Then Visit Our Official Channel YOUTUBE

Related Posts

One thought on “Split The String CodeChef Solution

  1. Have you ever thought about publishing an e-book or guest authoring on other websites? I have a blog based upon on the same subjects you discuss and would really like to have you share some stories/information. I know my viewers would appreciate your work. If you are even remotely interested, feel free to send me an e-mail.

Leave a Reply

Your email address will not be published.