1422. Maximum Score After Splitting a String - Detailed Explanation

Problem Statement

You are given a binary string s (a string consisting only of '0's and '1's). You must split s into two non-empty substrings:

• left substring (the beginning part)
• right substring (the remaining part)

The score of a split is defined as:

• Score = (Number of '0's in the left substring) + (Number of '1's in the right substring)

Your goal is to find the maximum possible score you can achieve by choosing an appropriate split point.

Example Inputs and Explanations

1. Example 1

   • Input: s = "011101"
   • Explanation:
     Consider splitting after the first character:
     • Left substring: "0" → contains 1 zero
     • Right substring: "11101" → contains 4 ones
     • Score = 1 + 4 = 5
   • Output: 5

2. Example 2

   • Input: s = "00111"
   • Explanation:
     One optimal split is after the second character:
     • Left substring: "00" → contains 2 zeros
     • Right substring: "111" → contains 3 ones
     • Score = 2 + 3 = 5
   • Output: 5

3. Example 3

   • Input: s = "1111"
   • Explanation:
     For a string with all ones, the only zeros come from the left substring if any—since there are none, you maximize the ones on the right.
     If you split after the first character:
     • Left substring: "1" → contains 0 zeros
     • Right substring: "111" → contains 3 ones
     • Score = 0 + 3 = 3
   • Output: 3

Constraints

• 2 <= s.length <= 500
• s consists of only '0' and '1' characters.
• Both substrings after splitting must be non-empty.

Hints Before Diving Into the Solution

• Hint 1:
  Think about what the score really represents. You are adding two counts:

  • The count of '0's from the left side.
  • The count of '1's from the right side.

• Hint 2:
  Consider precomputing the total number of '1's in the entire string. Then, as you move the split point from left to right, update:

  • A running count of '0's encountered (for the left substring).
  • A decrement in the total count of '1's when you pass a '1' (for the right substring).

This approach allows you to compute the score for each possible split efficiently.

Approaches to Solve the Problem

Approach 1: Brute Force

Idea

• For each possible split index:
  • Count the number of '0's in the left substring.
  • Count the number of '1's in the right substring.
  • Compute the score and track the maximum score.

Steps

1. Loop through every valid split index (from index 1 to n-1).
2. For each split, use two loops (or slicing with count operations) to count '0's and '1's.
3. Keep track of the maximum score found.

Drawbacks

• Time Complexity: O(n²) in the worst case because for each split you count characters in both substrings.
• Although acceptable for small strings (n ≤ 500), it is not optimal.

Approach 2: Optimal Single-Pass Solution

Idea

• Precompute the total count of '1's in the string.
• As you move the split index from left to right:
  • Maintain a running count of '0's for the left substring.
  • Adjust the right substring’s count of '1's by subtracting any '1' that you pass.
  • Compute the score at each split as (zeros count) + (remaining ones count) and update the maximum score.

Steps

1. Calculate totalOnes = total number of '1's in s.
2. Initialize zerosCount = 0 and maxScore = 0.
3. Iterate over the string from index 0 to n-2 (since both parts must be non-empty):
   • If s[i] is '0', increment zerosCount.
   • If s[i] is '1', decrement totalOnes (since this '1' moves from right to left).
   • Compute the current score as zerosCount + totalOnes.
   • Update maxScore if the current score is higher.
4. Return maxScore.

Advantages

• Time Complexity: O(n) because it uses a single pass.
• Space Complexity: O(1).

Step-by-Step Walkthrough with Visual Example

Let’s use the optimal approach on the example s = "011101".

1. Initial Calculation:

   • Total Ones (totalOnes): Count all '1's in the string → There are 4 ones.
   • Zeros Count (zerosCount): Start at 0.
   • maxScore: Initially 0.

2. Iterate over the string (valid indices 0 to 4):

   Index	Character	Action Taken	zerosCount	totalOnes (after update)	Score = zerosCount + totalOnes	maxScore
   0	'0'	Increment zerosCount	1	4	1 + 4 = 5	5
   1	'1'	Decrement totalOnes (pass a '1' to left)	1	3	1 + 3 = 4	5
   2	'1'	Decrement totalOnes	1	2	1 + 2 = 3	5
   3	'1'	Decrement totalOnes	1	1	1 + 1 = 2	5
   4	'0'	Increment zerosCount	2	1	2 + 1 = 3	5

3. Result: The maximum score found is 5.

Code Implementation

Python Implementation