56. Split a Binary String Into Maximum Number of Balanced Substrings

Given a binary string s, split it into the maximum possible number of contiguous, non-overlapping substrings such that each substring has an equal number of 0s and 1s (every character of s must belong to exactly one substring). Print that maximum count.

Input: A single line containing the binary string s. Output: Print a single integer - the maximum number of balanced substrings s can be split into.

1 <= |s| <= 10^5, total count of 0s in s equals total count of 1s

The problem guarantees the total count of 0s equals the total count of 1s in the whole string - this guarantees the running balance ALWAYS returns to exactly 0 by the very end, so the greedy cutting process is guaranteed to use up the entire string cleanly.

Split a binary string into as many pieces as possible, where every piece has an equal number of 0s and 1s. Brute force: Try every possible way of choosing cut points directly and check if each resulting piece is balanced - this branches combinatorially over all possible partition choices, impractical without a smarter approach. Optimised: A greedy approach works perfectly here: cutting the MOMENT the running balance returns to zero is always at least as good as waiting longer, since a later cut can only ever merge what could have been two valid pieces into one, never creating additional pieces - this greedy choice is provably optimal and needs only a single linear scan.

Scan the string once while maintaining a running balance that increases by 1 for '1' and decreases by 1 for '0'; every time this balance returns to exactly 0, that means the substring since the last cut is balanced, so close it off as one segment and increment the answer counter. This works because cutting as early as possible (the moment balance hits zero) can never do worse than waiting longer, since any longer balanced substring could always have been split into the earlier balanced piece plus a remainder that is itself still balanced. Time: O(n) Space: O(1)

Precompute prefix counts of 0s and 1s so the balance of any substring [i, j] can be checked in O(1), then use DP where dp[i] is the max number of balanced pieces achievable in the first i characters, trying every possible end point j > i for the next piece and taking dp[i] = max(dp[j]) + 1 wherever [i, j] is balanced. This avoids re-scanning substrings from scratch but still tries every candidate split point for each starting position. Time: O(n^2) Space: O(n)

Recursively try every possible way to place the next split boundary after the current position, check whether the resulting substring is balanced (equal 0s and 1s), and recurse on the remainder to maximize the count of balanced pieces. This explores an exponential number of ways to cut the string even though most cuts are never balanced. Time: O(2^n) Space: O(n) recursion depth

1. Scan the string left to right, keeping a running balance: add 1 for every '1' seen, subtract 1 for every '0'. 2. Every time this running balance returns exactly to 0, that marks the end of one valid, balanced piece - cut here and start counting the next piece fresh. 3. Count how many times this balance-returns-to-zero event happens across the whole string.

Time: O(n) - one single pass through the string, tracking a running balance counter. Space: O(1) - just the running balance and a cut counter.

Since 0-count must equal 1-count, the smallest valid s has length 2 (e.g. "01", giving 1 split) - test that; also test a fully alternating string like "0101...01" (splits into |s|/2 pieces), a string only splittable as one whole piece (e.g. "0011"), and |s|=10^5 for performance.

Be ready to justify WHY the greedy 'cut immediately when balance hits zero' strategy is provably optimal - a common interview follow-up is proving that waiting for a later zero-crossing can never produce MORE pieces than cutting immediately.