Problem Name: 1422. Maximum Score After Splitting a String
Problem Link: https://leetcode.com/problems/maximum-product-difference-between-two-pairs/
Difficulty: Easy
Tag: String
Language: C# | C++
OJ: LeetCode
Algorithm:
✅Initialization:
Initialize two arrays, left and right, to store the counts of '0's on the left and '1's on the right at each index.
Initialize two variables, leftValue and rightValue, to keep track of the counts of '0's and '1's while iterating through the string.
✅Left Count Calculation:
Iterate through the string from left to right.
If the current character is '0', increment leftValue.
Store the current value of leftValue in the left array at the corresponding index.
✅Right Count Calculation:
Iterate through the string from right to left.
If the current character is '1', increment rightValue.
Store the current value of rightValue in the right array at the corresponding index.
✅Score Calculation:
Iterate through the string from index 1 to s.Length - 2.
For each index i, calculate the score as the sum of '0's on the left (left[i]) and '1's on the right (right[i]).
Update the answer with the maximum score encountered during the iteration.
✅Handle Special Cases:
Check for special cases where the input string is "00", "01", "10", or "11" and return the corresponding predefined scores.
✅Return Result:
Return the calculated answer as the maximum score.
Code(C#)
public class Solution
{
public int MaxScore(string s)
{
var left = new int[s.Length];
var right = new int[s.Length];
int leftValue = 0;
int rightValue = 0;
int answer = 0;
for (int i=0; i<s.Length; i++)
{
if (s[i] == '0') leftValue++;
left[i] = leftValue;
}
for (int i = s.Length-1; i >= 0; i--)
{
if (s[i] == '1') rightValue++;
right[i] = rightValue;
}
for (int i = 1; i < s.Length-1; i++)
answer = Math.Max(answer, right[i] + left[i]);
if (s == "00") return 1;
if (s == "01") return 2;
if (s == "10") return 0;
if (s == "11") return 1;
return answer;
}
}
Code(C++)
Upcoming