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.
1#include <stdio.h>
2#include <string.h>
3
4int maxScore(char * s) {
5 int n = strlen(s);
6 int totalOnes = 0, leftZeros = 0, maxScore = 0;
7 for (int i = 0; i < n; i++) {
8 if (s[i] == '1') totalOnes++;
9 }
10 int rightOnes = totalOnes;
11 for (int i = 0; i < n - 1; i++) {
12 if (s[i] == '0') leftZeros++;
13 else rightOnes--;
14 int score = leftZeros + rightOnes;
15 if (score > maxScore) maxScore = score;
16 }
17 return maxScore;
18}
19
20int main() {
21 printf("%d\n", maxScore("011101")); // should output 5
22 printf("%d\n", maxScore("00111")); // should output 5
23 printf("%d\n", maxScore("1111")); // should output 3
24 return 0;
25}The program first computes the total number of ones in the whole string. Then it iterates through the string, maintaining counts of zeros in the left substring and ones in the right substring for each possible split, updating the maximum score accordingly.
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 JavaScript function optimally calculates the maximum score by iterating once through the string while managing counters for future splits and updating the score dynamically.