Maximum Score After Splitting A String

In this blog, you will learn how to get maximum score after splitting a given score string.

Introduction

 

In this article, we will solve the leetcode problem #1422, Maximum Score After Splitting a String. The problem statement goes like this,

 

Given a string s of zeros and ones, return the maximum score after splitting the string into two non-empty substrings (i.e. left substring and right substring). The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.

 

For example, if the string s is "011101", then the maximum score after spliting it will be 5. Let's explain that by taking all possible ways to split the string into two non-empty substrings as follows,

1. left = "0" and right = "11101", score = 1 + 4 = 5 
2. left = "01" and right = "1101", score = 1 + 3 = 4 
3. left = "011" and right = "101", score = 1 + 2 = 3 
4. left = "0111" and right = "01", score = 1 + 1 = 2 
5. left = "01110" and right = "1", score = 2 + 1 = 3 

And here is how the method is executed in C#,

static void Main(string[] args)
{
    var result = maxScore("011101");
    //result = 5
    result = maxScore("00111");
    //result = 5
    result = maxScore("1111");
    //result = 3
}

Solution

 

The most naive approach to this problem is by precomputing a prefix sum of ones ('1'). And then iterating from left to right counting the number of zeros ('0'), then using the precomputed prefix sum for counting ones ('1'). Update the answer.

 

Here is the C# code for the approach,

static int maxScore(string s)
{
    int zeroes = s.ElementAt(0) == '0' ? 1 : 0;
    int ones = 0;
    for (int i = 1; i < s.Length; i++)
    {
        if (s.ElementAt(i) == '1')
        {
            ones++;
        }
    }
    int maxScore = zeroes + ones;
    for (int i = 1; i < s.Length - 1; i++)
    {
        if (s.ElementAt(i) == '0')
        {
            zeroes++;
        }
        else
        {
            ones--;
        }
        maxScore = Math.Max(maxScore, zeroes + ones);
    }
    return maxScore;
}