Domain 1EasyCORE

Maximum Score After Splitting a String

The problem requires us to split a binary string `s` into two non-empty substrings such that the sum of zeros in the left substring and ones in the right substring is maximized. The input is a string `s` consisting only of '0's and '1's, with a length between 2 and 500 characters. The output should be an integer representing the maximum score achievable from all possible splits.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

1422. Maximum Score After Splitting a String

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 57.5%


Problem Breakdown

The problem requires us to split a binary string s into two non-empty substrings such that the sum of zeros in the left substring and ones in the right substring is maximized. The input is a string s consisting only of ‘0’s and ‘1’s, with a length between 2 and 500 characters. The output should be an integer representing the maximum score achievable from all possible splits.

Inputs:

  • A binary string s.

Outputs:

  • An integer representing the maximum score after splitting the string.

Implicit Constraints:

  • The string must be split into two non-empty substrings.
  • The length of the string is between 2 and 500, so a brute-force approach might not be efficient enough.

Intuition

A brute-force approach would involve iterating through all possible split points in the string, counting zeros in the left substring and ones in the right substring for each split, and keeping track of the maximum score. This approach has a time complexity of O(n^2), which is inefficient given the constraints.

The key insight to improve this is to realize that we can compute the total number of ‘1’s in the string once and then iterate through the string while maintaining a count of ‘0’s in the left substring. By doing so, we can calculate the score for each split point in constant time, resulting in an overall time complexity of O(n).

Approach

  1. Initialize Variables:

    • total_ones: Count the total number of ‘1’s in the string.
    • left_zeros: Initialize to 0, this will count the number of ‘0’s in the left substring as we iterate through the string.
    • max_score: Initialize to a very small number (or negative infinity), this will store the maximum score found.
  2. Iterate Through the String:

    • For each character in the string except the last one, update left_zeros if the character is ‘0’.
    • Calculate the current score as left_zeros + (total_ones - left_zeros).
    • Update max_score if the current score is greater than the previously recorded maximum score.
  3. Return the Maximum Score:

    • After iterating through the string, return max_score.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string. We iterate through the string once to count ‘1’s and then again to calculate the scores.
  • Space Complexity: O(1), as we use a constant amount of extra space regardless of the input size.

Solution

def maxScore(s: str) -> int:
    total_ones = s.count('1')
    left_zeros = 0
    max_score = float('-inf')
    
    for i in range(len(s) - 1):
        if s[i] == '0':
            left_zeros += 1
        current_score = left_zeros + (total_ones - left_zeros)
        max_score = max(max_score, current_score)
    
    return max_score

Edge Cases Handled

  • All ‘0’s: If the string consists entirely of ‘0’s, the maximum score will be achieved by splitting after the first character.
  • All ‘1’s: If the string consists entirely of ‘1’s, the maximum score will be achieved by splitting before the last character.
  • Single ‘0’ followed by ‘1’s: The split should occur after the single ‘0’.
  • Single ‘1’ followed by ‘0’s: The split should occur after the first ‘1’.

The solution correctly handles all edge cases and adheres to the problem constraints.