Maximum Score After Splitting a String

EASY

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.

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 <= 500
The string s consists of characters '0' and '1' only.

Approaches

Checkout 2 different approaches to solve Maximum Score After Splitting a String. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

The most straightforward approach is to simulate the splitting process for every possible position. The string can be split at any point from the first character to the second-to-last character, ensuring both left and right substrings are non-empty. For each split, we form the two substrings and manually count the zeros on the left and ones on the right to calculate the score. We keep track of the maximum score seen so far.

Algorithm

Initialize a variable maxScore to 0.
Loop through the string with an index i from 1 to length - 1. This index i marks the beginning of the right substring.
Inside the loop, for each i:
- Create the left substring s.substring(0, i).
- Create the right substring s.substring(i).
- Count the number of '0's in the left substring.
- Count the number of '1's in the right substring.
- Sum these counts to get the currentScore.
- Update maxScore with the maximum of maxScore and currentScore.
After the loop finishes, return maxScore.

We iterate through all possible split points. A string of length N has N-1 possible split points. For each split point i (from 1 to N-1), we consider s.substring(0, i) as the left part and s.substring(i) as the right part.

We then iterate through the left substring to count the number of '0's and through the right substring to count the number of '1's. The sum of these two counts gives the score for the current split. We compare this score with a maxScore variable, updating it if the current score is higher. This process is repeated for all possible splits.

For example, if s = "01101":

Split at i=1: left="0", right="1101". Zeros in left = 1, Ones in right = 3. Score = 4. maxScore = 4.
Split at i=2: left="01", right="101". Zeros in left = 1, Ones in right = 2. Score = 3. maxScore remains 4.
...and so on.

class Solution {
    public int maxScore(String s) {
        int maxScore = 0;
        int n = s.length();
        // Iterate through all possible split points
        for (int i = 1; i < n; i++) {
            String left = s.substring(0, i);
            String right = s.substring(i);
            
            int zerosLeft = 0;
            for (char c : left.toCharArray()) {
                if (c == '0') {
                    zerosLeft++;
                }
            }
            
            int onesRight = 0;
            for (char c : right.toCharArray()) {
                if (c == '1') {
                    onesRight++;
                }
            }
            
            int currentScore = zerosLeft + onesRight;
            maxScore = Math.max(maxScore, currentScore);
        }
        return maxScore;
    }
}

Complexity Analysis

Time Complexity: O(N^2), where N is the length of the string `s`. The main loop runs N-1 times. In each iteration, creating substrings and then iterating over them to count characters takes O(N) time, resulting in a total time complexity of O(N * N) = O(N^2).Space Complexity: O(N), because in each iteration of the loop, we create two new substrings. The combined length of these substrings is N, so the space required is proportional to N.

Pros and Cons

Pros:

Simple to conceptualize and implement.
Directly follows the problem definition.

Cons:

Inefficient due to repeated work. Counting characters in substrings within a loop leads to a quadratic time complexity.
Creating new substring objects in each iteration consumes extra memory.

Code Solutions

Checking out 3 solutions in different languages for Maximum Score After Splitting a String. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Maximum Score After Splitting a String

Patterns:

Prefix Sum

Data Structures:

String