# PROBLEM LINK:

# DIFFICULTY:

EASY-MEDIUM

# PREREQUISITES:

# PROBLEM:

Given a binary string S of length N, divide it into contiguous substrings, such that:

- the absolute difference between the number of 0's and 1's, in each substring, is \le K,
- the number of substrings is minimised.

# EXPLANATION:

Let an **optimal** partitioning of S (from left to right) be \{s_1,s_2,\dots,s_m\}.

Let the cost of a string be the number of 1's minus the number of 0's (not absolute difference).

**Observation:** The cost of s_1,s_2,\dots,s_m is **all** positive or **all** negative.

## Proof

We assume the contrary.

Then there exists some 1\le i < m, such that the parity of the costâ€™s of s_i and s_{i+1} is different. WLOG, let the costs of the strings be +a and -b respectively. From the definition, we know that 0\le a,b\le K.

Now, we can replace these two strings with a single string s_i+s_{i+1} and the partitioning will still be valid.

This is because the cost of the new string will be a+(-b) and by the above inequality, it is clear that -K\le a-b\le +K.

We have found a better solution (with one less substring), contradicting the optimality of \{s_1,\dots,s_m\}.

Contradiction and we are done.

WLOG, let the cost of all substrings be positive (the negative case can be handled similarly).

**Observation:** There exists an optimal partitioning such the cost of s_1,s_2,\dots,s_{m-1} is **exactly** +K.

## Proof

It is obvious that cost of s_i + cost of s_{i+1} should be greater than +K (and \le 2*K), else we can merge the two strings to get a better solution.

We prove by recursion. Consider an optimal partitioning \{s_1,\dots,s_m\}.

Now, while there exists some 1\le i< m such that, the cost of s_i is not equal to K, we can remove the first element of s_{i+1} and append it to the end of s_i. This works because:

- The partitioning is still valid (s_i and s_{i+1} are still valid, disjoint substrings). Also, when the cost of s_i is exactly K, 0< cost of s_{i+1} \le K - a direct consequence of the first statement.
- Every operation changes the cost by exactly 1. Thus, it is possible for us to stop when the cost is exactly +K (this will happen, since moving all elements from s_{i+1} to s_i will exceed the cost constraint).

Since in each move, an element moves to the previous substring and the number of substrings doesnâ€™t increase, the recursion is guaranteed to end. Thus, the entire algorithm can be done recursively to get a partitioning no worse than the original, that matches our above observation.

Thus, we have reduced the problem to partitioning S into substrings \{s_1,s_2,\dots,s_m\} such that, for each 1\le i < m, the cost of s_i is K (or -K for the negative case) and the value of m is minimised.

We solve this greedily. While S is non-empty, we -

- take the
**longest prefix**of S whose cost is \le K (or \ge -K for the negative case), - add the substring to our optimal partitioning, and
- erase the substring from S.

(The proof of the greedy approach is left to the reader as an exercise.)

With suitable pre-processing, it is possible to solve the problem in O(N).

## Implementation

Let F = \max\left(1,\left\lceil \frac{|\text{cost of S}|}{K} \right\rceil \right). It is evident that F is the number of substrings in the optimal partitioning.

Let c[i]\space (1\le i < F) be the largest value x\space (0\le x < N) such that the cost of prefix string S[0..x] is exactly K*i (or -K*i for the negative case). This can be computed using prefix sums in the following fashion:

- Iterate through the string (from left to right) - let the current index be x.
- Maintain a variable sum, equal to the cost of the prefix of S ending at x.
- If the value of sum equals K*i for some integer i, set the value of c[i] to x.

The first substring starts at S[0]. The j^{th}\space(2\le j \le F) substring starts at S[c[j-1]+1].

# TIME COMPLEXITY:

(Refer **Implementation** spoiler for terminologies).

Computing array c takes O(N) time. Generating the substrings takes O(F) time.

The final time complexity is thus:

# SOLUTIONS:

Editorialistâ€™s solution can be found here.

*Experimental:* For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

- 1
- 2
- 3
- 4
- 5

0 voters