Problem Description

You are given a string s consisting only of zeros ('0') and ones ('1'). Your task is to split this string into two non-empty parts (a left substring and a right substring) and calculate the maximum possible score.

The score is calculated as follows:

• Count the number of zeros in the left substring
• Count the number of ones in the right substring
• Add these two counts together to get the score

You need to find the maximum score possible among all valid ways to split the string.

For example, if s = "011101":

• If you split after the first character: left = "0", right = "11101"
  • Score = 1 zero in left + 4 ones in right = 5
• If you split after the second character: left = "01", right = "1101"
  • Score = 1 zero in left + 3 ones in right = 4
• If you split after the third character: left = "011", right = "101"
  • Score = 1 zero in left + 2 ones in right = 3

The constraint is that both parts must be non-empty, meaning you cannot take the entire string as left (leaving right empty) or take the entire string as right (leaving left empty).

Your goal is to return the maximum score achievable.

Intuition

The key insight is that we need to try every possible split position and find which one gives us the maximum score. Since we're splitting the string into two parts, we have n-1 possible positions to split (where n is the length of the string) - we can split after the 1st character, 2nd character, and so on, up to the second-to-last character.

A naive approach would be to actually split the string at each position and count zeros and ones in each part, but this would be inefficient. Instead, we can think about what happens as we move the split position from left to right:

• Initially, if we split after the first character, we have one character on the left and all remaining characters on the right
• As we move the split position one step to the right, we're essentially moving one character from the right substring to the left substring

This movement has a predictable effect on our score:

• If the character we're moving is a '0', it increases the left count (good for score) and doesn't affect the right count of ones
• If the character we're moving is a '1', it doesn't help the left count but decreases the right count of ones (bad for score)

So we can start by counting all the '1's in the string (this would be our right count if we split after the first character with an empty left count initially). Then, as we iterate through each potential split position:

• For each '0' we encounter, we increment our left count l by 1
• For each '1' we encounter, we decrement our right count r by 1
• At each position, we calculate the score as l + r and track the maximum

The expression int(x) ^ 1 is a clever way to count zeros: it converts '0' to 0 and '1' to 1, then XOR with 1 flips the bit (0 becomes 1, 1 becomes 0), effectively counting zeros instead of ones.

Learn more about Prefix Sum patterns.

Solution Approach

The solution implements a single-pass counting approach to find the maximum score efficiently.

Initialization:

• l = 0: Tracks the count of zeros in the left substring (initially empty)
• r = s.count("1"): Counts all ones in the string (initially all characters are in the right substring)
• ans = 0: Stores the maximum score found so far

Main Algorithm:

We iterate through the string from index 0 to n-2 (using s[:-1] to exclude the last character). This ensures both substrings remain non-empty after the split.

For each character x at position i:

1. Update left count: l += int(x) ^ 1

   • int(x) converts '0' to 0 and '1' to 1
   • XOR with 1 (^ 1) flips the bit: 0 becomes 1, 1 becomes 0
   • This effectively adds 1 to l if the character is '0', and adds 0 if it's '1'

2. Update right count: r -= int(x)

   • Subtracts 1 from r if the character is '1'
   • Subtracts 0 from r if the character is '0'
   • This removes the ones that have moved from right to left substring

3. Update maximum score: ans = max(ans, l + r)

   • Calculate the current score as the sum of zeros in left and ones in right
   • Keep track of the maximum score seen so far

Why this works:

At each iteration, we're conceptually moving the split position one character to the right. The character at position i moves from the right substring to the left substring. The counts are adjusted accordingly, and we check if this new split gives us a better score.

Time Complexity: O(n) where n is the length of the string - we make one initial pass to count ones and one main pass through the string.

Space Complexity: O(1) - we only use a constant amount of extra space for variables.

Example Walkthrough

Let's walk through the solution with s = "00111":

Initial Setup:

• l = 0 (no zeros counted in left substring yet)
• r = s.count("1") = 3 (all three ones are initially in the "right" side)
• ans = 0 (maximum score so far)

Iteration 1: Character at index 0 is '0'

• Split would be: left = "0" | right = "0111"
• l += int('0') ^ 1 = 0 ^ 1 = 1, so l = 1
• r -= int('0') = 0, so r = 3 (no ones moved out)
• Current score = l + r = 1 + 3 = 4
• ans = max(0, 4) = 4

Iteration 2: Character at index 1 is '0'

• Split would be: left = "00" | right = "111"
• l += int('0') ^ 1 = 0 ^ 1 = 1, so l = 2
• r -= int('0') = 0, so r = 3 (no ones moved out)
• Current score = l + r = 2 + 3 = 5
• ans = max(4, 5) = 5

Iteration 3: Character at index 2 is '1'

• Split would be: left = "001" | right = "11"
• l += int('1') ^ 1 = 1 ^ 1 = 0, so l = 2 (no change, not a zero)
• r -= int('1') = 1, so r = 2 (one '1' moved to left side)
• Current score = l + r = 2 + 2 = 4
• ans = max(5, 4) = 5

Iteration 4: Character at index 3 is '1'

• Split would be: left = "0011" | right = "1"
• l += int('1') ^ 1 = 1 ^ 1 = 0, so l = 2 (no change, not a zero)
• r -= int('1') = 1, so r = 1 (another '1' moved to left side)
• Current score = l + r = 2 + 1 = 3
• ans = max(5, 3) = 5

Result: The maximum score is 5, achieved when splitting after the second character ("00" | "111").

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. The algorithm performs the following operations:

• s.count("1") traverses the entire string once: O(n)
• The for loop iterates through n-1 characters of the string: O(n-1) = O(n)
• Each operation inside the loop (XOR, addition, subtraction, max comparison) takes constant time: O(1)

Therefore, the overall time complexity is O(n) + O(n) = O(n).

The space complexity is O(1). The algorithm only uses a fixed number of variables (l, r, ans, and x) regardless of the input size, requiring constant extra space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle Edge Cases with String Boundaries

A critical pitfall is iterating through the entire string instead of stopping at len(s) - 1. This would result in considering a split where the right substring is empty, which violates the problem constraint.

Incorrect Implementation:

# WRONG: This iterates through all characters including the last one
for i in range(len(s)):  # Bug: includes index len(s)-1
    char = s[i]
    # ... rest of the logic

Why it's wrong: When i = len(s) - 1, the split would be:

• Left substring: entire string s
• Right substring: empty string ""

This violates the "non-empty" constraint for both parts.

Correct Implementation:

# CORRECT: Stop before the last character
for i in range(len(s) - 1):  # Ensures right substring is never empty
    char = s[i]
    # ... rest of the logic

2. Incorrect Initial Score Calculation

Another common mistake is initializing max_score with the wrong value or forgetting that we need to actually check splits, not just initialize with a theoretical value.

Incorrect Implementation:

# WRONG: Assuming the initial state is a valid split
left_zeros = 0
right_ones = s.count("1")
max_score = left_zeros + right_ones  # Bug: This represents no split at all

Why it's wrong: The initial values left_zeros = 0 and right_ones = s.count("1") don't represent any actual split of the string - they represent a state where nothing is in the left substring.

Correct Implementation:

# CORRECT: Initialize max_score to 0 and let the loop find the actual maximum
max_score = 0
# The first iteration will set a valid initial score

3. Off-by-One Error in Character Movement Logic

A subtle pitfall is incorrectly updating the counters when moving a character from right to left.

Incorrect Implementation:

# WRONG: Decrementing right_ones for zeros too
for i in range(len(s) - 1):
    char = s[i]
    if char == "0":
        left_zeros += 1
        right_ones -= 1  # Bug: zeros don't affect right_ones count
    else:
        right_ones -= 1

Correct Implementation:

# CORRECT: Only decrement right_ones when moving a '1' from right to left
for i in range(len(s) - 1):
    char = s[i]
    if char == "0":
        left_zeros += 1
        # No change to right_ones (zeros don't count in right substring)
    else:
        right_ones -= 1  # Only decrease when moving a '1'