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 <iostream>
2#include <string>
3using namespace std;
4
5int maxScore(string s) {
6 int totalOnes = 0, leftZeros = 0, maxScore = 0;
7 for (const char& ch : s) {
8 if (ch == '1') totalOnes++;
9 }
10 int rightOnes = totalOnes;
11 for (size_t i = 0; i < s.length() - 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 cout << maxScore("011101") << endl; // Output: 5
22 cout << maxScore("00111") << endl; // Output: 5
23 cout << maxScore("1111") << endl; // Output: 3
24 return 0;
25}The code calculates the maximum score after splitting the string into two non-empty substrings by counting zeros from the left and ones from the right, updating the score dynamically.
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 C solution uses a single pass to calculate and update the maximum possible score by considering each zero incrementally in the left substring and decrementing from the total number of ones when a split is considered.