Maximum Score After Splitting a String

easy string prefix sum

Problem

Given a binary string s, split it into a non-empty left and right part. The score equals (zeros in left) + (ones in right). Return the maximum score.

Inputs = "011101"

Output5

Split after index 0: left "0" has 1 zero, right "11101" has 4 ones → 5.

s (binary)

def max_score(s):
    ones = s.count('1')
    zeros = 0
    best = 0
    for i in range(len(s) - 1):
        if s[i] == '0': zeros += 1
        else: ones -= 1
        best = max(best, zeros + ones)
    return best

function maxScore(s) {
  let ones = 0;
  for (const c of s) if (c === '1') ones++;
  let zeros = 0, best = 0;
  for (let i = 0; i < s.length - 1; i++) {
    if (s[i] === '0') zeros++;
    else ones--;
    best = Math.max(best, zeros + ones);
  }
  return best;
}

class Solution {
    public int maxScore(String s) {
        int ones = 0;
        for (char c : s.toCharArray()) if (c == '1') ones++;
        int zeros = 0, best = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) == '0') zeros++; else ones--;
            best = Math.max(best, zeros + ones);
        }
        return best;
    }
}

int maxScore(string s) {
    int ones = 0;
    for (char c : s) if (c == '1') ones++;
    int zeros = 0, best = 0;
    for (int i = 0; i < (int)s.size() - 1; i++) {
        if (s[i] == '0') zeros++; else ones--;
        best = max(best, zeros + ones);
    }
    return best;
}

Explanation

We need to try every place to cut the string and take the best score, but doing a fresh count at each cut would be slow. The trick is to keep running totals and update them as the split point slides right.

Start by counting all the 1s in the string into ones (treat everything as being on the right side at first), and set zeros = 0 for the empty left side.

Now move the split one character at a time. Each character we step over leaves the right side and joins the left. If it is a '0', the left side gains a zero, so zeros += 1. If it is a '1', the right side loses a one, so ones -= 1. The current score is just zeros + ones, and we track the best.

We stop before the last character so both sides stay non-empty. This way each split is updated in constant time from the previous one.

Example: s = "011101". Cutting right after the first 0 gives left "0" with 1 zero and right "11101" with 4 ones, scoring 5, which is the maximum.

Time: O(n) Space: O(1)