Split a binary string into two substrings with equal 0s and 1s
Problem
Split a binary string into the maximum number of consecutive pieces so that every piece has equal numbers of 0s and 1s. Return that count, or −1 if the whole string cannot be split this way.
Example 1
Input: "0100110101" Output: 4
"01" + "0011" + "01" + "01".
Also asked as: Split the Binary string into two substring with equal 0’s and 1’s
Test cases
Case 1
Input: "0100110101" Expected: 4
Case 2
Input: "0111100010" Expected: 3
Case 3
Input: "01" Expected: 1
Case 4
Input: "0000000000" Expected: -1
View solutionHide solution1 approach
1. Running counts
Time O(n)Space O(1)
Scan; every time zeros equals ones so far, you can cut. Count such cut points.
function maxSplits(s) { let zeros = 0, ones = 0, cuts = 0; for (const c of s) { c === '0' ? zeros++ : ones++; if (zeros === ones) cuts++; } return zeros === ones ? cuts : -1; // -1 if the whole string can't be balanced}