Sponsored
Sponsored
This approach involves calculating the cumulative sum of zeros from the start up to each point, and ones from the end at each point. For each possible split, compute the score using these pre-computed sums and track the maximum score.
Time Complexity: O(n), where n is the length of the string since it scans the string once.
Space Complexity: O(1), as it only uses variables for counting.
1function maxScore(s) {
2 let totalOnes = 0, leftZeros = 0, maxScore = 0;
3 for (let ch of s) {
4 if (ch === '1') totalOnes++;
5 }
6 let rightOnes = totalOnes;
7 for (let i = 0; i < s.length - 1; i++) {
8 if (s[i] === '0') leftZeros++;
9 else rightOnes--;
10 maxScore = Math.max(maxScore, leftZeros + rightOnes);
11 }
12 return maxScore;
13}
14
15console.log(maxScore("011101")); // Output: 5
16console.log(maxScore("00111")); // Output: 5
17console.log(maxScore("1111")); // Output: 3In this JavaScript implementation, we loop through the string to count the total number of ones and then calculate the score dynamically for each split point by adjusting counts of zeros and ones in the respective substrings.
This approach derives the solution in a single pass by calculating the score dynamically using prefix sum techniques. At each character, it updates the possible maximum score by subtracting a prefix count incrementally.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), since it uses only a few variables.
1
This Python function determines the maximum split score by leveraging a single pass through the string, updating the score dynamically based on left and right substring evaluations.