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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), since it uses only a few variables.
| 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. |
Maximum Score After Splitting a String - Leetcode 1422 - Python • NeetCodeIO • 13,199 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