LeetCode 1422 - Maximum Score After Splitting a String

LeetCode Problem 1422

Difficulty: 🟢 Easy
Topics: String, Prefix Sum

Solution

Problem Understanding

The problem gives us a binary string s, meaning the string contains only the characters '0' and '1'. We must split this string into two non-empty parts, a left substring and a right substring.

For every possible split position, we calculate a score defined as:

• the number of '0' characters in the left substring
• plus the number of '1' characters in the right substring

Our task is to return the maximum possible score among all valid splits.

A split can only happen between characters, and both sides must contain at least one character. If the string length is n, then valid split positions are from index 1 through n - 1.

For example, consider:

s = "011101"

If we split after the first character:

left  = "0"
right = "11101"

The left side contains one zero, and the right side contains four ones, so the score is:

1 + 4 = 5

We must check every possible split and determine the maximum score.

The constraints are small:

• 2 <= s.length <= 500

Since the string length is at most 500, even an O(n^2) solution would technically pass. However, the problem is designed to encourage a more efficient linear solution.

Several edge cases are important:

• A string containing all ones, such as "1111"
• A string containing many zeros at the beginning
• Very short strings of length 2
• Splits near the beginning or end of the string
• Ensuring both substrings remain non-empty

The problem guarantees the string contains only binary digits, so we never need to handle invalid characters.

Approaches

Brute Force Approach

The brute force solution tries every possible split position.

For each split:

1. Build the left substring.
2. Build the right substring.
3. Count zeros in the left substring.
4. Count ones in the right substring.
5. Compute the score.
6. Track the maximum score.

This approach is correct because it exhaustively checks every valid split and directly computes the score definition from the problem statement.

However, repeatedly scanning substrings becomes inefficient. If the string length is n, there are n - 1 split positions, and each split may require scanning up to n characters. This leads to O(n^2) time complexity.

Even though the constraints are small enough for this to pass, we can do better.

Optimal Approach

The key observation is that moving the split point from left to right changes the score in a predictable way.

Suppose we initially count all ones in the string except the first character's position. Then we move the split one character at a time.

When a character moves from the right substring to the left substring:

• If the character is '0', the left side gains one zero, so the score increases by 1.
• If the character is '1', the right side loses one one, so the score decreases by 1.

This means we can maintain the score incrementally instead of recomputing counts from scratch.

We only need:

• a running count of zeros on the left
• a running count of ones on the right
• the maximum score seen so far

This produces a linear time solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Recomputes counts for every split
Optimal	O(n)	O(1)	Maintains running counts while scanning once

Algorithm Walkthrough

1. Count the total number of '1' characters in the string.

This gives us the initial number of ones available on the right side before processing splits. 2. Initialize two variables:

• left_zeros = 0
• right_ones = total number of ones

These represent the current score components. 3. Iterate through the string from index 0 to n - 2.

We stop at n - 2 because the right substring must remain non-empty. 4. For each character:

• If the character is '0', increment left_zeros.
• If the character is '1', decrement right_ones.

This simulates moving the current character from the right substring into the left substring. 5. Compute the current score:

score = left_zeros + right_ones

6. Update the maximum score if the current score is larger.
7. After processing all valid split positions, return the maximum score.

Why it works

At every iteration, the algorithm maintains an invariant:

• left_zeros equals the number of zeros in the left substring
• right_ones equals the number of ones in the right substring

Since every valid split is processed exactly once, and the score for each split is computed correctly, the maximum recorded score must be the correct answer.

Python Solution

class Solution:
    def maxScore(self, s: str) -> int:
        right_ones = s.count("1")
        left_zeros = 0
        max_score = 0

        for i in range(len(s) - 1):
            if s[i] == "0":
                left_zeros += 1
            else:
                right_ones -= 1

            current_score = left_zeros + right_ones
            max_score = max(max_score, current_score)

        return max_score

The implementation begins by counting all ones in the string. Initially, every character belongs to the right substring, so this count represents the starting number of right-side ones.

The variable left_zeros starts at zero because the left substring is initially empty.

The loop iterates only to len(s) - 2, ensuring the right substring never becomes empty.

During each iteration:

• a zero increases the left contribution
• a one decreases the right contribution

The current score is computed immediately after updating the counts. The algorithm keeps track of the best score found so far using max_score.

Because the counts are updated incrementally, the solution avoids rescanning substrings and achieves linear performance.

Go Solution

func maxScore(s string) int {
	rightOnes := 0

	for _, ch := range s {
		if ch == '1' {
			rightOnes++
		}
	}

	leftZeros := 0
	maxScore := 0

	for i := 0; i < len(s)-1; i++ {
		if s[i] == '0' {
			leftZeros++
		} else {
			rightOnes--
		}

		currentScore := leftZeros + rightOnes

		if currentScore > maxScore {
			maxScore = currentScore
		}
	}

	return maxScore
}

The Go implementation follows the same logic as the Python solution.

One small difference is that Go strings are indexed as bytes. Since the string contains only ASCII characters '0' and '1', direct byte indexing with s[i] is completely safe and efficient.

No special handling for integer overflow is required because the maximum string length is only 500.

Worked Examples

Example 1

s = "011101"

Initial values:

right_ones = 4
left_zeros = 0
max_score = 0

Index	Character	left_zeros	right_ones	Score	max_score
0	0	1	4	5	5
1	1	1	3	4	5
2	1	1	2	3	5
3	1	1	1	2	5
4	0	2	1	3	5

Final answer:

5

Example 2

s = "00111"

Initial values:

right_ones = 3
left_zeros = 0
max_score = 0

Index	Character	left_zeros	right_ones	Score	max_score
0	0	1	3	4	4
1	0	2	3	5	5
2	1	2	2	4	5
3	1	2	1	3	5

Final answer:

5

Example 3

s = "1111"

Initial values:

right_ones = 4
left_zeros = 0
max_score = 0

Index	Character	left_zeros	right_ones	Score	max_score
0	1	0	3	3	3
1	1	0	2	2	3
2	1	0	1	1	3

Final answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	The string is scanned a constant number of times
Space	O(1)	Only a few integer variables are used

The algorithm performs one pass to count all ones and another pass to evaluate split positions. Since each pass is linear, the total time complexity remains O(n).

The solution uses only fixed-size integer variables regardless of input size, so the space complexity is constant.

Test Cases

solution = Solution()

assert solution.maxScore("011101") == 5  # Example 1
assert solution.maxScore("00111") == 5  # Example 2
assert solution.maxScore("1111") == 3   # Example 3

assert solution.maxScore("00") == 1     # Smallest all-zero string
assert solution.maxScore("11") == 1     # Smallest all-one string
assert solution.maxScore("01") == 2     # Perfect split
assert solution.maxScore("10") == 0     # No zeros left and no ones right

assert solution.maxScore("0000") == 3   # Best split before final character
assert solution.maxScore("10101") == 3  # Alternating pattern
assert solution.maxScore("010101") == 4 # Multiple optimal splits

assert solution.maxScore("000111") == 6 # Clear optimal midpoint split
assert solution.maxScore("110001") == 3 # Zeros clustered in middle
assert solution.maxScore("100001") == 5 # Large zero contribution on left

Test	Why
"011101"	Verifies standard mixed input
"00111"	Tests optimal split near middle
"1111"	Tests all ones
"00"	Smallest valid all-zero input
"11"	Smallest valid all-one input
"01"	Maximum possible score for length 2
"10"	Minimum possible score
"0000"	Tests all zeros
"10101"	Tests alternating digits
"010101"	Tests repeated transitions
"000111"	Tests balanced clustering
"110001"	Tests zeros concentrated in center
"100001"	Tests strong left-side zero accumulation

Edge Cases

All Ones

A string like "1111" can easily cause mistakes because the left substring never gains zeros. The score depends entirely on how many ones remain on the right side.

The implementation handles this correctly because every time a '1' moves to the left substring, right_ones decreases by one. The best split therefore occurs as early as possible.

All Zeros

A string like "0000" has no ones at all. A naive implementation might incorrectly assume the score must include at least one right-side one.

The algorithm works correctly because right_ones starts at zero and remains zero throughout the process. The score depends entirely on how many zeros accumulate on the left side.

Minimum Length Input

The smallest possible string length is 2. Examples include "01" and "10".

This case is important because there is only one valid split position. The loop condition range(len(s) - 1) correctly processes exactly one split and avoids invalid empty substrings.