Maximum Score After Splitting a String: Counting Zeros and Ones

You are given a binary string s (a string containing only '0' and '1' characters). You must split it into two non-empty substrings: a left part and a right part. The score of a split is the number of '0's in the left part plus the number of '1's in the right part. Return the maximum score among all possible splits.

This is LeetCode 1422: Maximum Score After Splitting a String, an easy problem that teaches you how to use prefix sums to efficiently evaluate every split point in a single pass.

The problem

You can split the string at any position from index 1 through n - 1 (both parts must be non-empty). For each split, you count zeros on the left and ones on the right, then add them together. Your goal is to find the split that maximizes this sum.

For example, given s = "011101", splitting after index 0 gives left = "0" and right = "11101". The left has 1 zero and the right has 4 ones, for a score of 5. That turns out to be the best split.

The brute force approach

The most direct approach is to try every possible split position. For each one, count the zeros in the left substring and the ones in the right substring. Track the maximum score seen.

def maxScore(s):
    best = 0
    for i in range(1, len(s)):
        left_zeros = s[:i].count('0')
        right_ones = s[i:].count('1')
        best = max(best, left_zeros + right_ones)
    return best

This works, but each call to count scans a portion of the string. Over all split positions, you end up doing O(n) work per split, giving O(n^2) total time.

The single-pass approach

You can do much better by noticing that as you move the split point one position to the right, only one character changes sides. If that character is a '0', the left gains a zero (score goes up by 1). If it is a '1', the right loses a one (score goes down by 1).

Start by counting all the ones in the entire string. That is your initial ones_right count. Set zeros_left to 0. Then sweep the split point from left to right. At each position, update the two counters and check if the new score is the best so far.

Step-by-step walkthrough

Let's trace through s = "011101". Total ones = 4, so ones_right starts at 4 and zeros_left starts at 0. We try each split point (the split must leave both parts non-empty, so we go from index 0 through index 4).

The code

def maxScore(s):
    ones_right = s.count('1')
    zeros_left = 0
    best = 0
    for i in range(len(s) - 1):
        if s[i] == '0':
            zeros_left += 1
        else:
            ones_right -= 1
        best = max(best, zeros_left + ones_right)
    return best

The loop runs from index 0 through len(s) - 2. This ensures the right part always has at least one character. At each step, the character at index i moves from the right side to the left side. If it is '0', that is a new zero on the left, so zeros_left increases. If it is '1', that is one fewer one on the right, so ones_right decreases. After updating, you check the current score against the best.

Complexity analysis

The brute force creates substrings and counts characters in each one, leading to quadratic time. The single-pass solution updates two counters incrementally, visiting each character exactly once (twice counting the initial count of ones). Space is constant because you only store zeros_left, ones_right, and best.

The building blocks

Prefix sum / running count

The core technique here is maintaining a running count as you sweep through the array. Instead of recomputing a count from scratch at every position, you update it incrementally. This turns an O(n) recomputation into O(1) per step.

count = 0
for i in range(n):
    if condition(arr[i]):
        count += 1

This pattern appears in problems like Range Sum Query, Subarray Sum Equals K, and Product of Array Except Self. Whenever you need to evaluate a quantity at every prefix or suffix, a running count (or prefix sum array) is the tool to reach for.

Complementary counters

In this problem you track two quantities that change in opposite directions. When one goes up, the other may go down. The score is the sum of both, and you want to maximize that sum. This "two counters, one split point" pattern shows up in problems like Partition Labels and Container With Most Water, where you sweep a boundary and track metrics on both sides.

Edge cases

All zeros "0000": every split gives zeros_left = k and ones_right = 0. The best score equals the length of the left part, which is maximized at n - 1 (leaving one character on the right). For "0000", the answer is 3.

All ones "1111": every split gives zeros_left = 0 and ones_right = n - k. The best score equals the length of the right part, maximized at n - 1. For "1111", the answer is 3.

Single zero at start "01111": splitting after index 0 gives 1 zero + 4 ones = 5. Every other split loses ones on the right without gaining zeros. The answer is 5.

Length 2 "01" or "10": only one possible split. For "01", score = 1 + 1 = 2. For "10", score = 0 + 0 = 0.

From understanding to recall

You have seen how a simple running-count trick turns an O(n^2) problem into O(n). The idea is clean: count all ones first, then sweep left to right, transferring characters from right to left and adjusting counters. But writing it correctly under pressure requires remembering the loop bounds (stop one before the end) and the update logic (increment zeros or decrement ones, never both).

Spaced repetition is the bridge between understanding and fluency. You practice writing this prefix-sum sweep from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "maximize a score across all split points" and the two-counter approach flows out naturally.

CodeBricks breaks this problem into its prefix sum and complementary counter building blocks, then drills them independently. You type each piece from memory until the loop bounds, counter updates, and edge-case handling are second nature. When a split-point optimization question appears in your interview, you do not need to re-derive the approach. You just write it.

Related posts

• Count Binary Substrings - Another problem analyzing groups of 0s and 1s in binary strings
• Number of 1 Bits - Counting bits with different techniques
• Split a String in Balanced Strings - Another string splitting optimization problem