Maximum Score After Splitting a String Leetcode Solution

Difficulty Level Easy
Frequently asked in Google
algorithms coding Interview interviewprep LeetCode LeetCodeSolutions StringViews 2115

The problem Maximum Score After Splitting a String Leetcode Solution provided us with a string. The given string contains only 0 and 1. So one can also consider it as a binary sequence. The problem then asked us to find the maximum score achievable after splitting the string. After splitting the string, the score is evaluated as the number of 0s in the left part and the number of 1s in the right half. So as usual, before diving into the solution. Let us take a look at a few examples.

s = "011101"
5

Explanation: One can easily see that the maximum score possible can be attained if we split the string after the first index. That way we have four 1s in the right half and a single 0 in the left half.

Maximum Score After Splitting a String Leetcode Solution

s = "00111"
5

Explanation: One can easily figure out that if we split the string such that the left half contained all the 0s and the other half contained all the 1s. That way we will obtain the maximum score. So, it’s easy to see that the point of splitting should be at index 2.

Approach for Maximum Score After Splitting a String Leetcode Solution

The problem Maximum Score After Splitting a String Leetcode Solution has already been stated above in the problem description. In brief, the problem asked us to find the maximum score that can be attained if we split the string into two halves. The score is evaluated as per the number of 0s in left half and 1s in right half. So, first, we calculate the total number of zeros and ones in the given string. In the second loop, we keep on calculating the number 0f 0s encountered so far.

We are using this loop to simulate the process of splitting the string. We store the zeros and ones encountered so far. The ones in the right half can be easily calculated by subtracting the number of 1s in the left half. We keep on updating the answer with the maximum value that can be attained.

Code for Maximum Score After Splitting a String Leetcode Solution

C++ code

#include <bits/stdc++.h>
using namespace std;

int maxScore(string s) {
    int zero = 0, one = 0;
    for(int i=0;i<s.size();i++)
        (s[i] == '0') ? zero++ : one++;
    int curZero = (s[0] == '0'), curOne = (s[0] == '1');
    int ans = curZero + one - curOne;
    for(int i=1;i<s.size()-1;i++){
        (s[i] == '0') ? curZero++ : curOne++;
        ans = max(ans, curZero + one - curOne);
    }
    return ans;
}

int main(){
    cout<<maxScore("00111");
}

5

Java code

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int maxScore(String s) {
        int one = 0, zero = 0;
        for(int i=0;i<s.length();i++)
            if(s.charAt(i) == '0')
                zero++;
            else
                one++;
        int curZero = (s.charAt(0) == '0' ? 1 : 0), curOne = (s.charAt(0) == '1' ? 1 : 0);
        int ans = curZero + one - curOne;
        for(int i=1;i<s.length()-1;i++){
            if(s.charAt(i) == '0')curZero++;
            else curOne++;
            ans = Math.max(ans, curZero + one-curOne);
        }
        return ans;
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    System.out.print(maxScore("00111"));
  }
}
5

Complexity Analysis

Time Complexity

O(N), even though the approach is two-pass, The time complexity still remains to be linear.

Space Complexity

O(1), because constant space is used in the algorithm.

Translate »