Maximum Score After Splitting a String

Difficulty: Easy | Acceptance: 65.10% | Paid: No Topics: String, Prefix Sum

Given a string s of zeros and ones, return the maximum score after splitting the string into two non-empty substrings (i.e. left substring and right substring).

The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.

• Examples
• Constraints
• Brute Force
• Prefix Sum
• One Pass Optimization

Examples

Example 1:

Input: s = "011101"
Output: 5
Explanation: 
All possible splits:
"0" | "11101": 1 + 4 = 5
"01" | "1101": 1 + 3 = 4
"011" | "101": 1 + 2 = 3
"0111" | "01": 1 + 1 = 2
"01110" | "1": 1 + 1 = 2

Example 2:

Input: s = "00111"
Output: 5
Explanation: 
"0" | "0111": 1 + 3 = 4
"00" | "111": 2 + 3 = 5
"001" | "11": 2 + 2 = 4
"0011" | "1": 2 + 1 = 3

Example 3:

Input: s = "1111"
Output: 3

Constraints

2 <= s.length <= 500
s[i] is either '0' or '1'.

Brute Force

Intuition Iterate through every possible split point. For each split, count the zeros in the left part and the ones in the right part to calculate the score.

Steps

• Iterate through the string from index 1 to length - 1.
• For each index, split the string into left and right substrings.
• Count zeros in the left substring.
• Count ones in the right substring.
• Update the maximum score found so far.

class Solution:
    def maxScore(self, s: str) -> int:
        n = len(s)
        max_score = 0
        for i in range(1, n):
            left = s[:i]
            right = s[i:]
            score = left.count('0') + right.count('1')
            max_score = max(max_score, score)
        return max_score

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Simple to implement but inefficient for large strings due to repeated counting.

Prefix Sum

Intuition Precompute the number of zeros up to each index (prefix sum) and the number of ones from each index to the end (suffix sum). This allows O(1) score calculation for any split.

Steps

• Create an array prefixZeros where prefixZeros[i] stores the count of zeros in s[0...i].
• Create an array suffixOnes where suffixOnes[i] stores the count of ones in s[i...n-1].
• Iterate through all possible split points. For a split at index i, the score is prefixZeros[i-1] + suffixOnes[i].
• Track the maximum score.

class Solution:
    def maxScore(self, s: str) -> int:
        n = len(s)
        prefix_zeros = [0] * n
        suffix_ones = [0] * n
        
        count = 0
        for i in range(n):
            if s[i] == '0':
                count += 1
            prefix_zeros[i] = count
            
        count = 0
        for i in range(n - 1, -1, -1):
            if s[i] == '1':
                count += 1
            suffix_ones[i] = count
            
        max_score = 0
        for i in range(1, n):
            score = prefix_zeros[i-1] + suffix_ones[i]
            max_score = max(max_score, score)
            
        return max_score

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Faster than brute force but uses extra space for the prefix and suffix arrays.

One Pass Optimization

Intuition We can calculate the score in a single pass. First, count the total number of ones in the string. Then, iterate through the string. Maintain a count of zeros seen so far. As we move the split point, if we see a ‘0’, it adds to the left score. If we see a ‘1’, it means that ‘1’ is moving from the right side to the left side, so we decrement the total ones count (which represents the right side score).

Steps

• Count the total number of ‘1’s in the string.
• Initialize zeros to 0 and maxScore to 0.
• Iterate through the string from index 0 to n - 2 (to ensure the right substring is non-empty).
• If the current character is ‘0’, increment zeros.
• If the current character is ‘1’, decrement totalOnes.
• Calculate the current score as zeros + totalOnes and update maxScore.

class Solution:
    def maxScore(self, s: str) -> int:
        total_ones = s.count('1')
        zeros = 0
        max_score = 0
        
        for i in range(len(s) - 1):
            if s[i] == '0':
                zeros += 1
            else:
                total_ones -= 1
            
            max_score = max(max_score, zeros + total_ones)
            
        return max_score

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Optimal solution with linear time complexity and constant space usage.