Proficient.
Put your skills to the test.

Problem summary

Split a binary string containing equally many zeroes and ones into as many consecutive nonempty balanced substrings as possible.

Constraints

2 ≤ string length ≤ 1,000,000; the length is even and counts of 0 and 1 are equal.

Worked example

An independently prepared example for this explanation.

001101

2

Solution analysis

1. Assign +1 to 1 and −1 to 0. A substring is balanced exactly when its two endpoint prefix balances agree.
2. Because the first prefix balance is zero, the end of every balanced block in any valid split must also have prefix balance zero. Therefore cut after every return to zero.
3. For 001101, balances are −1,−2,−1,0,−1,0. The two returns produce 0011 | 01. For 111000 the balance returns to zero only at the end, so just one block is possible.

Why it works

Every valid cut must occur at a zero prefix balance, since the concatenation of the preceding balanced blocks is balanced. Conversely consecutive zero-balance prefixes enclose a balanced substring. Cutting at all such positions is feasible and uses every possible cut, so no other split has more blocks.

Watch out. Count the final return to zero as a block. Do not cut where counts happen to match only after resetting to a nonzero global balance.

An independently written complete program with standard headers.

#include<iostream>
#include<string>
// Algorithm: Assign +1 to 1 and −1 to 0.
using namespace std;
int main(){
    string text;
    cin>>text;
    int balance=0;
    int blocks=0;
    for(char symbol:text){
        balance+=symbol=='1'?1:-1;
        if(balance==0){
            blocks++;
        }
    }
    cout<<blocks<<'\n';
}