Given a binary string s, split it into a non-empty left and non-empty right part. The score is: number of zeros in the left part plus number of ones in the right part. Return the maximum score over all valid splits.

Engineering takeaway. This problem looks like it needs a scan per split point (O(n²)), but the score can be maintained incrementally in one pass. The pattern — compute a global count, then walk a pointer while updating two running counters — shows up constantly in streaming and windowing logic.

Intuition

Imagine the split point moving from left to right, one character at a time. Two things change on each step:

  • If the new left character is 0, the left score grows by 1.
  • If it's 1, it leaves the right side, so the right score shrinks by 1.

If we precompute the total number of ones up front, we never need to re-scan the right half. The right count is just "total ones minus the ones already consumed by the left."

Approach

  1. left = 0 — zeros accumulated on the left.
  2. right = total ones in the string — the initial right-side count.
  3. Iterate up to the second-to-last character:
    • 0 → left += 1
    • 1 → right -= 1
    • score = left + right; keep the max.

We stop at length - 1 because both parts must be non-empty.

function maxScore(s: string): number {
  let left = 0;
  let right = s.split("").reduce((sum, ch) => sum + parseInt(ch, 10), 0);
  let result = 0;
 
  for (let i = 0; i < s.length - 1; i++) {
    if (s[i] === "0") {
      left += 1;
    } else {
      right -= 1;
    }
    result = Math.max(result, left + right);
  }
 
  return result;
}

Complexity

  • Time: O(n) — a single pass.
  • Space: O(1) — just two counters.

The lesson

Whenever a "score" can be expressed as something already computed plus something still remaining, maintain it as a running value instead of recomputing it. That single idea is the difference between an O(n²) brute force and an O(n) solution.