Maximum Score After Splitting a String

How it works

We can derive a single-pass solution using algebra. The score at position i equals left_zeros + right_ones. Since right_ones = total_ones - left_ones, the score becomes left_zeros + total_ones - left_ones, or equivalently total_ones + (left_zeros - left_ones). Since total_ones is constant, we only need to maximize (left_zeros - left_ones) while iterating, then add the total ones at the end.

Steps

1. Process the first character to initialize zeros and ones counters.
2. Iterate from index 1 to n-1:
   • Update the maximum of (zeros - ones) before processing the current character.
   • Update counters based on whether the current character is '0' or '1'.
3. Return result + ones (where ones now contains the total count).

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Allowing Empty Substrings

The problem requires both left and right substrings to be non-empty. Splitting at index 0 (empty left) or index n (empty right) is invalid. The loop should iterate from index 1 to n-1, not from 0 to n. Forgetting this constraint leads to incorrect boundary cases.

Counting Characters in the Wrong Substring

When computing the score, zeros should be counted in the left substring only, and ones should be counted in the right substring only. A common mistake is counting ones on the left or zeros on the right, which inverts the logic and produces wrong results.

class Solution:
    def maxScore(self, s: str) -> int:
        # res = Max of all (left_zeros + right_ones)
        # res = Max of all (left_zeros + (total_ones - left_ones))
        # res = total_ones (constant) + Max of all (left_zeros - left_ones)

        zeros = 0
        ones = 0

        if s[0] == '0':
            zeros += 1
        else:
            ones += 1

        res = float('-inf')
        for i in range(1, len(s)):
            res = max(res, zeros - ones)
            if s[i] == '0':
                zeros += 1
            else:
                ones += 1

        return res + ones

class Solution {
public:
    int maxScore(string s) {
        // res = Max of all (leftZeros + rightOnes)
        // res = Max of all (leftZeros + (totalOnes - leftOnes))
        // res = totalOnes (constant) + Max of all (leftZeros - leftOnes)

        int zeros = 0, ones = 0, res = INT_MIN;

        if (s[0] == '0') {
            zeros++;
        } else {
            ones++;
        }

        for (int i = 1; i < s.size(); i++) {
            res = max(res, zeros - ones);
            if (s[i] == '0') {
                zeros++;
            } else {
                ones++;
            }
        }

        return res + ones;
    }
};