Problem Description
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.
Key Insights
- The string can be split at any point between the first and last character.
- The score is calculated as the sum of the number of zeros in the left substring and the number of ones in the right substring.
- By iterating through the string while maintaining counts of zeros and ones, we can efficiently compute scores for each possible split.
Space and Time Complexity
Time Complexity: O(n) - We iterate through the string once to calculate scores. Space Complexity: O(1) - We use a constant amount of space for counters.
Solution
To solve this problem, we can use a single pass approach. We'll maintain two counters: one for the number of zeros in the left substring (left_zeros) and another for the number of ones in the right substring (right_ones). We initialize right_ones with the total number of ones in the string. As we iterate through the string, we increment left_zeros for each '0' in the left substring and decrement right_ones for each '1' in the right substring. At each valid split point, we calculate the score and keep track of the maximum score encountered.