Here is an explanation of the C++ solution for LeetCode 1422: Maximum Score After Splitting a String. The objective is to split a binary string s into two non-empty substrings (left and right) and find the maximum sum of zeros in the left substring and ones in the right substring.
Algorithm Intuition
A naive solution would compute the scores for each split point independently, resulting in an $O(N^2)$ time complexity. However, we can optimize this to a single pass ($O(N)$) by pre-counting the total number of ones in the string. As we iterate from left to right, we move elements into the left split, dynamically adjusting our count of zeros (increasing) and ones (decreasing).
C++ Code
class Solution {
public:
int maxScore(string s) {
int ones = count(s.begin(), s.end(), '1'); // Total 1's in the string
int zeros = 0, result = 0;
for (int i = 0; i < s.size() - 1; i++) { // Exclude the last split point to keep both parts non-empty
if (s[i] == '1')
ones--; // 1 is moved from the right to the left split
else
zeros++; // Increment zero count in the left split
result = max(result, zeros + ones); // Track max score
}
return result;
}
};
Complexity
- Time Complexity: $O(N)$ time complexity as we make a single initial pass to count the ones, and one final pass to evaluate the optimal split.
- Space Complexity: $O(1)$ constant auxiliary space.