1422. Maximum Score After Splitting a String
Problem Description
Given a string s consisting of zeros and ones, the task is to split the string into two non-empty substrings (left and right) such that the score is maximized. The score is calculated as the number of zeros in the left substring plus the number of ones in the right substring.
Example:
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
Solution Code
class Solution {
public int maxScore(String s) {
int totalOnes = 0;
for (char c : s.toCharArray()) {
if (c == '1') {
totalOnes++;
}
}
int maxScore = 0;
int zeros = 0;
int ones = totalOnes;
for (int i = 0; i < s.length() - 1; i++) {
if (s.charAt(i) == '0') {
zeros++;
} else {
ones--;
}
maxScore = Math.max(maxScore, zeros + ones);
}
return maxScore;
}
}
Approach Name
Prefix Sum Approach
Intuition
The problem requires us to find the maximum score obtained by splitting the string into two non-empty substrings. The score is the sum of the number of zeros in the left substring and the number of ones in the right substring.
To optimize this, we can precompute the total number of ones in the string. Then, as we iterate through the string, we can keep track of the number of zeros in the left substring and the number of ones in the right substring. By updating these counts as we move through the string, we can efficiently compute the score for each possible split and keep track of the maximum score.
Algorithm
- Count Total Ones: First, count the total number of ones in the string.
- Initialize Counts: Initialize counters for zeros in the left substring and ones in the right substring.
- Iterate Through String: Iterate through the string (excluding the last character to ensure both substrings are non-empty).
- If the current character is ‘0’, increment the zeros count.
- If the current character is ‘1’, decrement the ones count.
- Calculate the score for the current split and update the maximum score if this score is higher.
- Return Maximum Score: After iterating through the string, return the maximum score found.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string. We traverse the string twice: once to count the total number of ones and once to compute the maximum score.
- Space Complexity: O(1), as we are using a constant amount of extra space regardless of the input size.