Compute the Maximum Score After Splitting a String

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.

Hints:
Precompute a prefix sum of ones (‘1’).
Iterate from left to right counting the number of zeros (‘0’), then use the precomputed prefix sum for counting ones (‘1’). Update the answer.

Prefix Sum Algorithm to compute the Maximum Score After Splitting a String

We can compute the total number of ‘1’s using the std::accumulate() function from C++. Then, we can iterate from right to left, and count the number of ‘1’s in the right partition. Then the score can be computed because we can easily get the number of ‘0’s in the left partition.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int maxScore(string s) {
        int sum = std::accumulate(begin(s), end(s), 0, [](auto &a, auto &b) {
            return a + (b == '1' ? 1 : 0);
        });
        if (sum == 0) return 1;
        if (sum == s.size()) return sum - 1;
        int res = 0, right = 0;
        for (int i = s.size() - 1; i > 0; -- i) {
            right += (s[i] == '1' ? 1 : 0);
            int score = (i - sum  + right) + right;
            res = max(res, score);
        }
        return res;
    }
};

class Solution {
public:
    int maxScore(string s) {
        int sum = std::accumulate(begin(s), end(s), 0, [](auto &a, auto &b) {
            return a + (b == '1' ? 1 : 0);
        });
        if (sum == 0) return 1;
        if (sum == s.size()) return sum - 1;
        int res = 0, right = 0;
        for (int i = s.size() - 1; i > 0; -- i) {
            right += (s[i] == '1' ? 1 : 0);
            int score = (i - sum  + right) + right;
            res = max(res, score);
        }
        return res;
    }
};

The runtime complexity is O(N) where we perform two linear scans. The space requirement is constant.

–EOF (The Ultimate Computing & Technology Blog) —