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.
1using System;
2
3class Program {
4 public static int MaxScore(string s) {
5 int totalOnes = 0, leftZeros = 0, maxScore = 0;
6 foreach (char ch in s) {
7 if (ch == '1') totalOnes++;
8 }
9 int rightOnes = totalOnes;
10 for (int i = 0; i < s.Length - 1; i++) {
11 if (s[i] == '0') leftZeros++;
12 else rightOnes--;
13 maxScore = Math.Max(maxScore, leftZeros + rightOnes);
14 }
15 return maxScore;
16 }
17
18 static void Main(string[] args) {
19 Console.WriteLine(MaxScore("011101")); // Output: 5
20 Console.WriteLine(MaxScore("00111")); // Output: 5
21 Console.WriteLine(MaxScore("1111")); // Output: 3
22 }
23}This C# solution evaluates the maximum score possible by splitting the string while maintaining a running count of zeros in the left and ones in the right subsequences. It updates the maximum score accordingly as it iterates through the string.
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 Java solution achieves the maximum score by splitting the string iteratively while maintaining and updating count of zeros and ones to efficiently compute the score in one pass.