Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1422. Maximum Score After Splitting a String - Leetcode Solution

Code Implementation

class Solution:
    def maxScore(self, s: str) -> int:
        max_score = 0
        left_zeros = 0
        right_ones = s.count('1')
        # We cannot split at the last character
        for i in range(len(s)-1):
            if s[i] == '0':
                left_zeros += 1
            else:
                right_ones -= 1
            max_score = max(max_score, left_zeros + right_ones)
        return max_score
      
class Solution {
public:
    int maxScore(string s) {
        int max_score = 0;
        int left_zeros = 0;
        int right_ones = count(s.begin(), s.end(), '1');
        // Cannot split at the last character
        for (int i = 0; i < s.size() - 1; ++i) {
            if (s[i] == '0') left_zeros++;
            else right_ones--;
            max_score = max(max_score, left_zeros + right_ones);
        }
        return max_score;
    }
};
      
class Solution {
    public int maxScore(String s) {
        int maxScore = 0;
        int leftZeros = 0;
        int rightOnes = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') rightOnes++;
        }
        // Cannot split at the last character
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) == '0') leftZeros++;
            else rightOnes--;
            maxScore = Math.max(maxScore, leftZeros + rightOnes);
        }
        return maxScore;
    }
}
      
var maxScore = function(s) {
    let maxScore = 0;
    let leftZeros = 0;
    let rightOnes = 0;
    for (let c of s) {
        if (c === '1') rightOnes++;
    }
    // Cannot split at the last character
    for (let i = 0; i < s.length - 1; i++) {
        if (s[i] === '0') leftZeros++;
        else rightOnes--;
        maxScore = Math.max(maxScore, leftZeros + rightOnes);
    }
    return maxScore;
};

Problem Description

Given a binary string s (a string only containing '0' and '1'), you want to split it into two non-empty substrings at some index. The score for a split is the number of '0's in the left substring plus the number of '1's in the right substring. Your task is to return the maximum possible score you can get from any valid split. Note that you cannot split at the last character (both substrings must be non-empty).

Thought Process

When first approaching this problem, you might think about checking every possible split, counting zeros on the left and ones on the right for each. But this would be inefficient for long strings. Instead, we should look for a way to efficiently track the number of zeros and ones as we move the split point from left to right, so we don't recount every time. By updating counts as we scan, we can avoid redundant work and make the solution much faster.

Solution Approach

To solve the problem efficiently, we:
  • First, count the total number of '1's in s. This will be our initial count of ones on the right side.
  • Initialize a variable for counting zeros on the left (left_zeros) and set it to 0.
  • Iterate through the string from the first character up to the second-to-last character (since both sides must be non-empty).
  • At each character:
    • If it's '0', increment left_zeros (since this zero will be on the left after the split).
    • If it's '1', decrement right_ones (since this one will move from right to left after the split).
  • After updating counts at each step, compute the current score as left_zeros + right_ones and update the maximum score found so far.
  • Return the maximum score after the loop.
This approach only requires a single pass through the string (after the initial count), making it efficient and simple.

Example Walkthrough

Let's take s = "011101" as an example.
  • Total ones: 4 (positions 1,2,3,5)
  • We try splits after each character (positions 0 to 4):
  • Split after 0: left = "0" (1 zero), right = "11101" (4 ones), score = 1+4=5
  • Split after 1: left = "01" (1 zero), right = "1101" (3 ones), score = 1+3=4
  • Split after 2: left = "011" (1 zero), right = "101" (2 ones), score = 1+2=3
  • Split after 3: left = "0111" (1 zero), right = "01" (1 one), score = 1+1=2
  • Split after 4: left = "01110" (2 zeros), right = "1" (1 one), score = 2+1=3
  • The highest score is 5, achieved by splitting after the first character.
This matches what our algorithm will compute step by step, updating zero and one counts as it goes.

Time and Space Complexity

  • Brute-force Approach: For each of the n-1 split points, count zeros and ones in both substrings, which is O(n) per split, so O(n^2) time.
  • Optimized Approach: We make a single pass to count ones (O(n)), then another single pass to update and compute the score (O(n)), so total time is O(n).
  • Space Complexity: Both approaches use O(1) extra space (just counters), ignoring input size.
The optimized solution is much faster and suitable for large strings.

Summary

The key insight is to avoid recounting zeros and ones for every split by updating counters as we scan through the string. By using two variables to track zeros on the left and ones on the right, we can efficiently calculate the score for each split in a single pass. This makes the solution both elegant and highly efficient.