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.
1public class Main {
2 public static int maxScore(String s) {
3 int totalOnes = 0, leftZeros = 0, maxScore = 0;
4 for (char ch : s.toCharArray()) {
5 if (ch == '1') totalOnes++;
6 }
7 int rightOnes = totalOnes;
8 for (int i = 0; i < s.length() - 1; i++) {
9 if (s.charAt(i) == '0') leftZeros++;
10 else rightOnes--;
11 maxScore = Math.max(maxScore, leftZeros + rightOnes);
12 }
13 return maxScore;
14 }
15
16 public static void main(String[] args) {
17 System.out.println(maxScore("011101")); // Output: 5
18 System.out.println(maxScore("00111")); // Output: 5
19 System.out.println(maxScore("1111")); // Output: 3
20 }
21}This solution uses a for-each loop to count the total number of '1's and iteratively calculates the score for each potential split position, maintaining a running count of zeros on the left and ones on the right of that position.
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
class ProgramSinglePass {
public static int MaxScoreSinglePass(string s) {
int leftZeros = 0, rightOnes = 0, maxScore = 0;
foreach (char ch in s) {
if (ch == '1') rightOnes++;
}
for (int i = 0; i < s.Length - 1; i++) {
if (s[i] == '0') leftZeros++;
else rightOnes--;
maxScore = Math.Max(maxScore, leftZeros + rightOnes);
}
return maxScore;
}
static void Main(string[] args) {
Console.WriteLine(MaxScoreSinglePass("011101")); // Output: 5
Console.WriteLine(MaxScoreSinglePass("00111")); // Output: 5
Console.WriteLine(MaxScoreSinglePass("1111")); // Output: 3
}
}This C# code finds the maximum possible score by assessing each possible split point and using running counts of zeros and ones in a single linear pass.