Split a binary string into two substrings with equal 0s and 1s

Easy

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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
}