1422. Maximum Score After Splitting a String - Explanation

Problem Link



1. Brute Force

Intuition

The score at any split point is the sum of zeros in the left substring plus the sum of ones in the right substring. The simplest approach is to try every valid split position and count directly. For each split, we scan the left portion to count zeros and the right portion to count ones, then track the maximum score found.

Algorithm

  1. Iterate through each valid split position i from index 1 to n-1 (both substrings must be non-empty).
  2. For each split position:
    • Count zeros in the left substring (indices 0 to i-1).
    • Count ones in the right substring (indices i to n-1).
    • Calculate the score as the sum of these two counts.
  3. Track and return the maximum score across all split positions.
class Solution:
    def maxScore(self, s: str) -> int:
        n, res = len(s), 0
        for i in range(1, n):
            left_zero = 0
            for j in range(i):
                if s[j] == '0':
                    left_zero += 1
            right_one = 0
            for j in range(i, n):
                if s[j] == '1':
                    right_one += 1
            res = max(res, left_zero + right_one)
        return res

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(1)O(1)

2. Prefix & Suffix Arrays

Intuition

Instead of recounting zeros and ones for every split position, we can precompute cumulative counts. A prefix array stores the count of zeros up to each index, while a suffix array stores the count of ones from each index to the end. This way, evaluating any split becomes an O(1) lookup.

Algorithm

  1. Build a prefix array left_zero where left_zero[i] holds the count of zeros from index 0 to i.
  2. Build a suffix array right_one where right_one[i] holds the count of ones from index i to n-1.
  3. For each valid split position i (from 1 to n-1):
    • The score is left_zero[i-1] + right_one[i].
  4. Return the maximum score found.
class Solution:
    def maxScore(self, s: str) -> int:
        n = len(s)
        left_zero = [0] * n
        right_one = [0] * n

        if s[0] == '0':
            left_zero[0] = 1
        for i in range(1, n):
            left_zero[i] = left_zero[i - 1]
            if s[i] == '0':
                left_zero[i] += 1

        if s[n - 1] == '1':
            right_one[n - 1] = 1
        for i in range(n - 2, -1, -1):
            right_one[i] = right_one[i + 1]
            if s[i] == '1':
                right_one[i] += 1

        res = 0
        for i in range(1, n):
            res = max(res, left_zero[i - 1] + right_one[i])
        return res

Time & Space Complexity

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

3. Iteration (Two Pass)

Intuition

We can avoid storing full arrays by maintaining running counts. First, count all ones in the string. Then iterate through the string, incrementing zeros and decrementing ones as we move the split point. At each position, the current counts represent exactly what we need for the score calculation.

Algorithm

  1. Count the total number of ones in the string.
  2. Initialize zero = 0 to track zeros seen so far.
  3. Iterate from index 0 to n-2 (last valid split position):
    • If the current character is '0', increment zero.
    • Otherwise, decrement one (this one moves from right to left portion).
    • Update the result with zero + one.
  4. Return the maximum score.
class Solution:
    def maxScore(self, s: str) -> int:
        zero = 0
        one = s.count('1')
        res = 0

        for i in range(len(s) - 1):
            if s[i] == '0':
                zero += 1
            else:
                one -= 1
            res = max(res, zero + one)

        return res

Time & Space Complexity

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

4. Iteration (One Pass)

Intuition

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.

Algorithm

  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).
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

Time & Space Complexity

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