#1422

Easy

LeetCode Problem Workspace

Maximum Score After Splitting a String

Find the optimal split point in a binary string to maximize zeros on the left and ones on the right efficiently.

Problem Statement

Given a binary string s consisting only of '0' and '1', determine the maximum score obtainable by splitting the string into two non-empty substrings. The score is defined as the number of zeros in the left substring plus the number of ones in the right substring.

You must return the highest possible score achievable across all valid splits. Constraints: 2 <= s.length <= 500, and s contains only '0' and '1'. For example, given s = "011101", the optimal split yields a score of 5.

Examples

Example 1

Input: s = "011101"

Output: 5

All possible ways of splitting s into two non-empty substrings are: left = "0" and right = "11101", score = 1 + 4 = 5 left = "01" and right = "1101", score = 1 + 3 = 4 left = "011" and right = "101", score = 1 + 2 = 3 left = "0111" and right = "01", score = 1 + 1 = 2 left = "01110" and right = "1", score = 2 + 1 = 3

Example 2

Input: s = "00111"

Output: 5

When left = "00" and right = "111", we get the maximum score = 2 + 3 = 5

Example 3

Input: s = "1111"

Output: 3

Example details omitted.

Constraints

2 <= s.length <= 500
The string s consists of characters '0' and '1' only.

Solution Approach

Use a Prefix Sum of Ones

Precompute a prefix sum array where prefix[i] stores the number of ones in s[0..i]. This allows you to quickly determine the number of ones on the right for any split without recalculating.

Iterate Over Split Points

For each index from 1 to s.length - 1, count zeros in the left substring and use the prefix sum to get ones in the right substring. Update a maximum score variable whenever a higher score is found.

Return the Maximum Score

After checking all possible splits, return the highest score found. This approach guarantees O(n) time and O(1) extra space if the prefix sum is computed inline.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The solution runs in O(n) time because it traverses the string once to compute prefix sums and once to evaluate all split points. Space is O(1) if prefix sums are computed on the fly, otherwise O(n) for a dedicated array.

What Interviewers Usually Probe

Do you consider all split points including minimal left and right substrings?
Have you optimized the calculation of ones on the right using prefix sums?
Can you explain why recomputing counts at every split is inefficient?

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle both substrings as non-empty when iterating split points.
Recalculating right-side ones for each split instead of using a prefix sum.
Miscounting zeros in the left substring when updating the score.

Follow-up variants

Compute the minimum score after splitting a string with the same zero-left, one-right rule.
Given a ternary string '0', '1', '2', maximize zeros-left plus ones-right plus twos-right.
Allow splitting into more than two substrings and compute the maximum combined score.

FAQ

What is the main strategy for Maximum Score After Splitting a String?

The main strategy is to iterate through all split points while maintaining counts of zeros on the left and ones on the right using prefix sums.

Can this problem be solved without prefix sums?

Yes, but recomputing ones on the right for each split increases time complexity to O(n^2), which is inefficient for longer strings.

Why is it important to ensure both substrings are non-empty?

Splits that create empty substrings violate the problem constraints and would produce invalid scores.

What is the time and space complexity of the optimal solution?

Time complexity is O(n) due to a single pass over the string for prefix sums and split evaluation. Space is O(1) if prefix sums are computed inline.

Does the pattern 'String plus Prefix Sum' apply here?

Yes, this problem exemplifies the 'String plus Prefix Sum' pattern by using prefix sums to efficiently compute right-side counts in linear time.

terminal

Solution

Solution 1: Counting

We use two variables $l$ and $r$ to record the number of 0s in the left substring and the number of 1s in the right substring, respectively. Initially, $l = 0$, and $r$ is equal to the number of 1s in the string $s$.

1

2

3

4

5

6

7

8

9

class Solution:
    def maxScore(self, s: str) -> int:
        l, r = 0, s.count("1")
        ans = 0
        for x in s[:-1]:
            l += int(x) ^ 1
            r -= int(x)
            ans = max(ans, l + r)
        return ans

Continue Practicing

#1371 find the longest substring containing vowels in even counts #1208 get equal substrings within budget #1177 can make palindrome from substring