1. Problem Definition & Mathematical Reduction

Let the input string s have length N. A valid split point is an index i such that the left substring spans s[0 ... i] and the right substring spans s[i + 1 ... N - 1], where 0 ≤ i < N - 1 (both left and right partitions must be strictly non-empty).

The objective function to maximize is:

Let $Z_L(i)$ represent the count of zeros in the left partition, $O_R(i)$ represent the count of ones in the right partition, and $O_{total}$ represent the total count of ones in the entire string. Notice the crucial relationship:

Substituting this identity into our score equation reveals an elegant algebraic simplification:

Because $O_{total}$ is an invariant constant for any given string, maximizing the split score is mathematically equivalent to maximizing the running difference $(Z_L(i) - O_L(i))$! This reduction enables us to track the maximum score dynamically in a single pass.

2. Algorithmic Approaches: O(N^2) Brute Force vs. O(N) Optimal

Approach 1: Naive Quadratic Scan (O(N^2))

For every split index i from 0 to N - 2, iterate through the left slice to count zeros, then iterate through the right slice to count ones. Repeating this scan for all N - 1 split positions requires $sum_{i=1}^{N-1} O(N) = O(N^2)$ time. For strings of length $10^5$, this triggers severe CPU timeouts.

Approach 2: Two-Pass Prefix Sum (O(N) Time, O(1) Space)

In Pass 1, traverse the string once to count the total number of ones ($O_{total}$). In Pass 2, maintain a running tally of zeros in the left partition ($Z_L$) and decrement the remaining ones in the right partition ($O_R$) whenever encountering a '1'. Update the maximum score at each step. This achieves $O(N)$ time with zero extra heap allocations.

Approach 3: Single-Pass Algebraic Maximization (O(N) Time, O(1) Space)

By leveraging the formula $Score(i) = O_{total} + (Z_L(i) - O_L(i))$, we can compute the maximum difference $(Z_L(i) - O_L(i))$ in the initial pass. In the final element ($i = N - 1$), we update $O_{total}$ and add it to our stored maximum difference, completing the entire operation in a single traversal.

3. Production-Grade Implementations

TypeScript Implementation (Single-Pass Algebraic Optimization)

/**
 * LeetCode 1422: Maximum Score After Splitting a String
 * Time Complexity: O(N) | Auxiliary Space: O(1)
 */
export function maxScore(s: string): number {
  let zeros = 0;
  let ones = 0;
  let maxDiff = -Infinity;

  // Single pass through s[0 ... N - 2]
  for (let i = 0; i < s.length - 1; i++) {
    if (s[i] === '0') {
      zeros++;
    } else {
      ones++;
    }
    // Track maximum of (zeros_left - ones_left)
    maxDiff = Math.max(maxDiff, zeros - ones);
  }

  // Account for the final character to get total ones
  if (s[s.length - 1] === '1') {
    ones++;
  }

  // Score = total_ones + max(zeros_left - ones_left)
  return ones + maxDiff;
}

Modern C++20 Implementation

#include <string_view>
#include <algorithm>
#include <climits>

class Solution {
public:
    int maxScore(std::string_view s) {
        int zeros = 0;
        int ones = 0;
        int maxDiff = INT_MIN;

        // Iterate up to the second-to-last character (non-empty partitions)
        for (size_t i = 0; i < s.size() - 1; ++i) {
            if (s[i] == '0') {
                zeros++;
            } else {
                ones++;
            }
            maxDiff = std::max(maxDiff, zeros - ones);
        }

        // Account for final character
        if (s.back() == '1') {
            ones++;
        }

        return ones + maxDiff;
    }
};

Python 3 Implementation

class Solution:
    def maxScore(self, s: str) -> int:
        zeros = 0
        ones = 0
        max_diff = float('-inf')

        for char in s[:-1]:
            if char == '0':
                zeros += 1
            else:
                ones += 1
            max_diff = max(max_diff, zeros - ones)

        if s[-1] == '1':
            ones += 1

        return ones + max_diff

4. Complexity Proof & Edge Case Resilience

• Time Complexity: O(N): The string of length N is traversed exactly once. Each character involves constant-time integer increments, subtractions, and maximum comparisons. Zero additional passes or nested iterations occur.
• Auxiliary Space Complexity: O(1): Only four primitive integer registers (zeros, ones, maxDiff, loop counter) are allocated on the execution stack. Memory consumption remains strictly constant regardless of input length.

Defensive Edge Cases

• Minimum Length ($N = 2$): For "00", split at index 0 produces left "0" (score 1) and right "0" (score 0), returning 1. For "11", left "1" (score 0) and right "1" (score 1) yields 1. For "01", left "0" (1) and right "1" (1) yields optimal 2.
• All Zeros ("0000"): Best split index is $N - 2$, maximizing left zeros while right has 0 ones, returning $N - 1$.
• All Ones ("1111"): Best split index is 0, having 0 left zeros and $N - 1$ right ones, returning $N - 1$.