We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Score After Splitting a String

Number: 1537

Difficulty: Easy

Paid? No

Companies: Google, Meta, Bloomberg, Amazon, Adobe

Problem Description

Given a string s consisting of characters '0' and '1', the task is to split the string into two non-empty substrings (a left and a right) such that the score is maximized. The score is defined as the number of zeros in the left substring plus the number of ones in the right substring.

Key Insights

  • The split can occur at any index from 1 to n-1 (where n is the length of the string) to ensure both substrings are non-empty.
  • Pre-calculate the total number of ones in the original string.
  • As you iterate through possible splits, maintain a running count of zeros seen so far (for the left substring) and ones seen so far. The ones in the right substring can be computed as (total ones - ones in the left substring).
  • The maximum score is obtained by iteratively checking the score at each split position.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, because we scan the string once. Space Complexity: O(1), as only a few counters are used.

Solution

We approach the problem using a single pass. First, count the total number of ones in the string. Then, iterate through the string (except for the last character to ensure the right substring is non-empty) and maintain two counters: one for zeros (left score contribution) and one for ones (to subtract from total ones for the right substring). At each index, the score is computed as (zeros_count + (totalOnes - ones_count)). We update the maximum score seen. This efficient use of prefix sum ideas allows us to compute the answer in O(n) time using constant extra space.

Code Solutions

# Python code solution with line-by-line comments

def maxScore(s):
    # Count the total number of ones in the string for right substring calculations.
    totalOnes = s.count('1')
    
    max_score = 0  # To keep track of the maximum score found.
    zeros_count = 0  # Counter for zeros in the left substring.
    ones_count = 0   # Counter for ones encountered (to subtract from totalOnes for the right substring).
    
    # Iterate through the string but not including the last character to ensure right substring is non-empty.
    for i in range(len(s) - 1):
        # If current character is zero, it contributes to the left score.
        if s[i] == '0':
            zeros_count += 1
        else:
            # Current character is one; update ones_count which will reduce right side ones.
            ones_count += 1
        
        # Calculate current score:
        # Left substring's score is zeros_count and right substring's score is totalOnes - ones_count.
        current_score = zeros_count + (totalOnes - ones_count)
        # Update max_score if current_score is higher.
        max_score = max(max_score, current_score)
    
    return max_score

# Example usage:
if __name__ == "__main__":
    s = "011101"
    print(maxScore(s))  # Expected output: 5
← Back to All Questions