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.
Example 1:
Input: s = "011101" Output: 5 Explanation: 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 Explanation: When left = "00" and right = "111", we get the maximum score = 2 + 3 = 5
Example 3:
Input: s = "1111" Output: 3
Constraints:
2 <= s.length <= 500s consists of characters '0' and '1' only.Problem Overview: You get a binary string s. Split it into two non-empty parts. The score equals the number of 0s in the left substring plus the number of 1s in the right substring. Your task is to find the split position that produces the maximum score.
The brute idea is simple: try every possible split and count zeros and ones on each side. But repeated counting leads to unnecessary work. The key insight is that the score can be computed incrementally if you track counts using prefix sum style preprocessing or by updating the score during a single scan.
Approach 1: Prefix Sum Approach (O(n) time, O(n) space)
Precompute counts so each split can be evaluated in constant time. Build a prefix array where prefixZero[i] stores the number of zeros from index 0 to i. Similarly track the total number of ones or compute a suffix-style value for ones on the right. For every split position i (between i and i+1), the score becomes prefixZero[i] + (totalOnes - onesPrefix[i]). Iterate through all valid split points and keep the maximum. This method uses the classic prefix sum technique and works well when you want clear precomputation and constant-time queries for each position in a string. Time complexity is O(n) because the string is scanned a few times, and space complexity is O(n) for the prefix arrays.
Approach 2: Single Pass Score Calculation (O(n) time, O(1) space)
The optimal approach avoids extra arrays. First count the total number of ones in the entire string. That represents the initial potential contribution of the right side. Then iterate from left to right, stopping before the last character so the right substring remains non-empty. When you encounter a 0, the left score increases by one. When you encounter a 1, the right side loses one because that 1 moves to the left partition. At each position compute currentScore = zerosLeft + onesRight and update the maximum. This technique effectively simulates all splits while maintaining running counts. Time complexity is O(n) and space complexity is O(1), making it the most efficient approach for large inputs.
Recommended for interviews: Start by explaining the idea of evaluating every split and how repeated counting would be inefficient. Then move to the prefix-sum reasoning to show how preprocessing removes redundant work. Finally present the single-pass method. Interviewers usually expect the O(n), O(1) solution because it demonstrates that you can transform prefix counting logic into an in-place running calculation.
This approach involves calculating the cumulative sum of zeros from the start up to each point, and ones from the end at each point. For each possible split, compute the score using these pre-computed sums and track the maximum score.
The program first computes the total number of ones in the whole string. Then it iterates through the string, maintaining counts of zeros in the left substring and ones in the right substring for each possible split, updating the maximum score accordingly.
Time Complexity: O(n), where n is the length of the string since it scans the string once.
Space Complexity: O(1), as it only uses variables for counting.
This approach derives the solution in a single pass by calculating the score dynamically using prefix sum techniques. At each character, it updates the possible maximum score by subtracting a prefix count incrementally.
This C solution uses a single pass to calculate and update the maximum possible score by considering each zero incrementally in the left substring and decrementing from the total number of ones when a split is considered.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), since it uses only a few variables.
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.
We traverse the first n - 1 characters of the string s. For each position i, if s[i] = 0, then l is incremented by 1; otherwise, r is decremented by 1. Then we update the answer to be the maximum value of l + r.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Prefix Sum Approach | Time Complexity: O(n), where n is the length of the string since it scans the string once. |
| Single Pass Score Calculation | Time Complexity: O(n), where n is the length of the string. |
| Counting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Sum Approach | O(n) | O(n) | Useful when demonstrating prefix-sum logic or when multiple range queries are needed. |
| Single Pass Score Calculation | O(n) | O(1) | Best choice for interviews and production due to constant space and a single traversal. |
Maximum Score After Splitting a String - Leetcode 1422 - Python • NeetCodeIO • 13,929 views views
Watch 9 more video solutions →Practice Maximum Score After Splitting a String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor