1422. Maximum Score After Splitting a String

EasyString

Problem Description

In this problem, we are given a string s consisting of characters '0' and '1'. Our goal is to split this string into two non-empty parts, a left and a right substring, such that the score obtained from the split is maximized. The score is calculated as the number of '0' characters in the left substring added to the number of '1' characters in the right substring. We need to determine the maximum score we can achieve by splitting the string s. It's important to note that the split must result in non-empty substrings, which means we can split the string anywhere between the first and last character.

Intuition

To solve this problem, we need to understand that the split will always be between two characters in the string. In terms of index i, the left substring will include characters from index 0 to i, and the right substring will include characters from index i+1 to the end. Our goal is to maximize the sum of zeros in the left substring and ones in the right substring.

A straightforward approach would be to check all possible splits and calculate the score for each, but that would be inefficient. Instead, we can take advantage of the fact that any split only moves one character from one substring to the other, thus changing the score by either 1 or -1. This allows us to iteratively calculate the score for all possible splits in a single pass through the string after an initial count.

Here's the step-by-step intuition:

Start by calculating the initial score, which is the number of '0's in the first position plus the number of '1's in the rest of the string (since the first character must be in the left substring for it to be non-empty).
Initialize the maximum score ans with this initial score.
Iterate over the string starting from the second character to the second-to-last character, updating the current score t and maximum score ans as follows:
- If we find a '0', it means moving the split to the right would bring one more '0' to the left substring, so we increase t by 1.
- If we find a '1', it means moving the split to the right would take one '1' out of the right substring, so we decrease t by 1.
- After each update, compare t with the current ans and update ans if t is higher.
Once we've considered all splits, the ans variable will hold the maximum score possible.

This solution has a linear time complexity because we go through the string only once after the initial count, making it an efficient approach.

Solution Approach

The solution utilizes a simple yet efficient algorithm that takes advantage of the cumulative property of scores during the split process. Let's delve into the key aspects of the implementation:

Initializing Scores:
- The initial score t is computed by checking if the first character is '0' and adding it to the count of '1's in the rest of the string. This is because we want all '0's to be in the left substring and '1's to be in the right one to maximize the score.
- The Python expression (s[0] == '0') returns True if the first character is '0' and False otherwise. Since True equates to 1 and False to 0 in Python, this expression conveniently adds 1 to the count if the first character is '0'.
- The count of '1's in the right substring is calculated using s[1:].count('1'), where s[1:] is the substring excluding the first character.
Iterating over Characters:
- A for loop is used to iterate through each character in the string starting from index 1 and ending at the second-last character, since we are only interested in valid splits (non-empty left and right substrings).
- During each iteration, the variable t is updated to reflect the new score if the split were to occur right after the current character. If s[i] is '0', t is incremented by 1 because we'd have one more '0' in the left substring. Conversely, if s[i] is '1', t is decremented by 1 because we'd have one less '1' in the right substring.
Updating Maximum Score:
- The maximum score so far is kept in the variable ans. After each score update, ans is set to the maximum of itself and the current score t by executing ans = max(ans, t).
Return Final Score:
- After the loop completes, the maximum score ans is returned.

By using a single pass through the string and updating scores incrementally, this solution achieves a time complexity of O(n), where n is the length of the string. The space complexity is O(1) since only a fixed number of variables are used.

We use no additional data structures; instead, we capitalize on the fact that iterating over the string while tracking the current score and the maximum score suffices to solve the problem. The pattern used here involves greedy local optimizations at each character index that leads to a global optimization, i.e., the maximum score.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example string s = "011101" to illustrate the solution approach step-by-step:

Initializing Scores:
- We start by calculating the initial score t for the first possible split, which will have all characters in the left substring except the first one on the right side.
- With our example, the first character is '0', so according to the logic, (s[0] == '0') will be True, and thus t starts at 1.
- Then, we count the number of '1's in the rest of the string ("11101"), which is 4. So, the initial score t is 1 + 4 = 5.
- We also initialize the maximum score ans to this initial value, ans = 5.
Iterating over Characters:
- We start processing the string from the second character to the second-to-last character.
- As we move to the next character, which is '1', the score t does not change as per the rule because '1' is already in the right substring. Therefore, t remains 5 and ans remains 5.
- The next character is '1' again, and nothing changes for the same reason, so t and ans are still 5.
- The fourth character is '1', and again, nothing changes, so t and ans remain 5.
- Now, the fifth character is '0'. If we were to split here, the '0' would move to the left substring. This means we add 1 to t, making t = 5 + 1 = 6. We compare this with ans and since t is greater, we update ans to 6.
- Moving to the final character, '1', if we were to split here, we would subtract 1 from t because the '1' would move out of the right substring. This gives us t = 6 - 1 = 5. ans remains 6 since it was not exceeded.
Updating Maximum Score:
- Throughout the process, ans is updated to the maximum score encountered during each iteration. The maximum score that we calculated in the example was 6.
Return Final Score:
- After the loop, we conclude that the maximum score that can be achieved by splitting the string s = "011101" is 6. This is the value stored in ans, which is what our function would return.

Solution Implementation

1class Solution:
2    def max_score(self, s: str) -> int:
3        # Initial score considers the first character '0' as +1 and counts '1's in the rest of the string.
4        score = (s[0] == '0') + s[1:].count('1')
5        # Initialized answer with the initial score.
6        max_score = score
7      
8        # Loop through the string starting from the second character to the second to last.
9        for i in range(1, len(s) - 1):
10            # If the character is '0', increment score, if '1', decrement it.
11            score += 1 if s[i] == '0' else -1
12            # Update max_score if the current score is greater.
13            max_score = max(max_score, score)
14      
15        # Return the maximum score achieved.
16        return max_score
17

1class Solution {
2    public int maxScore(String s) {
3        // Initialize total score for the first partition
4        int totalScore = 0;
5        // If the first character is '0', increase the score by 1
6        if (s.charAt(0) == '0') {
7            totalScore++;
8        }
9        // Calculate initial score for '1's in the string, skipping the first character
10        for (int i = 1; i < s.length(); ++i) {
11            if (s.charAt(i) == '1') {
12                totalScore++;
13            }
14        }
15        // The best score is initially set to the score from the initial partition
16        int maxScore = totalScore;
17      
18        // Iterate through the string to find partitions and track the highest score
19        for (int i = 1; i < s.length() - 1; ++i) {
20            // If the current character is '0', increase the total score
21            // If it is '1', decrease the total score
22            totalScore += (s.charAt(i) == '0') ? 1 : -1;
23            // Update the maximum score if the current total score is greater
24            maxScore = Math.max(maxScore, totalScore);
25        }
26        // Return the highest score found amongst all possible partitions
27        return maxScore;
28    }
29}
30

1class Solution {
2public:
3    int maxScore(string s) {
4        // Initialize totalScore to 0. It will represent the total score while traversing the string.
5        int totalScore = 0;
6      
7        // If the first character is '0', we increment totalScore as we get one point for it.
8        if (s[0] == '0') {
9            ++totalScore;
10        }
11      
12        // Add to totalScore the number of '1' in the string, except for the first character.
13        for (int i = 1; i < s.size(); ++i) {
14            totalScore += s[i] == '1';
15        }
16      
17        // Initialize maxScore with the totalScore calculated so far.
18        int maxScore = totalScore;
19      
20        // Start traversing the string from the second character to the second-to-last.
21        for (int i = 1; i < s.size() - 1; ++i) {
22            // Increment totalScore if it's a '0', else decrement it for a '1'.
23            totalScore += s[i] == '0' ? 1 : -1;
24          
25            // Update maxScore with the higher value between maxScore and totalScore.
26            maxScore = max(maxScore, totalScore);
27        }
28      
29        // Return the maximum score found.
30        return maxScore;
31    }
32};
33

1function maxScore(s: string): number {
2    const stringLength = s.length; // Store the length of the input string
3    let maxResult = 0;            // Initialize the variable to hold the maximum score
4    let currentScore = 0;         // Initialize the variable to hold the current score
5
6    // First, we check if the first character is '0' to possibly increase the current score,
7    // because we are looking for the maximum number of '0's in the left partition
8    // and the maximum number of '1's in the right partition of the string after a split.
9    if (s[0] === '0') {
10        currentScore++;
11    }
12
13    // Calculate the score of 1's in the right partition by iterating over the string
14    // starting at index 1 (second character) because the left partition will have at least
15    // one character.
16    for (let i = 1; i < stringLength; i++) {
17        if (s[i] === '1') {
18            currentScore++;
19        }
20    }
21
22    // Initially set the maximum score to the score calculated above
23    maxResult = Math.max(maxResult, currentScore);
24
25    // Loop through s, starting from the second character to the second-to-last character
26    // since we need to split s into two non-empty partitions.
27    for (let i = 1; i < stringLength - 1; i++) {
28        // If the current character is '0', we add one to the current score
29        // because we are effectively moving a '0' from the right partition (initially the whole string sans the first character)
30        // to the left partition, increasing the left partition's score.
31        if (s[i] === '0') {
32            currentScore++;
33        // If the current character is '1', we subtract one from the current score
34        // because we are moving a '1' from the right partition to the left one,
35        // decreasing the right partition's score.
36        } else if (s[i] === '1') {
37            currentScore--;
38        }
39        // Update the maximum result if the current score is greater
40        maxResult = Math.max(maxResult, currentScore);
41    }
42
43    // Finally return the maximum score found, which corresponds to the
44    // best place to split string s into two partitions
45    return maxResult;
46}
47

Time and Space Complexity

Time Complexity

The time complexity is determined by how many operations the algorithm performs in relation to the input size, which is the length of the string s in this case.

First, the algorithm initializes ans and t with the count of '1's in the substring s[1:] and checks if s[0] is '0'. This takes O(n) time where n is the length of s, as count('1') iterates through the string once.
Then, there's a loop which iterates n - 2 times (the string length minus 2, as the loop starts at 1 and ends at len(s) - 1). Each iteration performs a constant amount of work by checking s[i] and possibly updating t and ans.
Combining both steps, the total number of operations is proportional to 2n - 2.

Since these are linear operations, the time complexity of the algorithm is O(n).

Space Complexity

The space complexity is determined by the amount of extra storage the algorithm uses in relation to the input size.

The algorithm uses a fixed number of integer variables ans, t, and i, which use a constant amount of space.
There is no use of any data structure that grows with the input size.

Therefore, the space complexity is O(1), as the amount of extra space used does not depend on the size of the input.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don’t know