Maximum Score After Splitting a String

Easy
362.

Maximum Score After Splitting a String

Maximum Score After Splitting a String is an easy coding problem on strings and prefix sum, asked in Amazon and Adobe interviews.

Given a string s of zeros and ones, split it into two non-empty parts, left and right.

The score of a split is the number of zeros in the left part plus the number of ones in the right part. Return the maximum score.

Example 1

Input
s = "011101"
Output
5
Explanation
Splitting after the first character gives 1 zero on the left and 4 ones on the right.

Example 2

Input
s = "00111"
Output
5

Example 3

Input
s = "1111"
Output
3
Explanation
The left part must be non-empty, so one 1 is always sacrificed.

Constraints

  • 2 <= s.length <= 40
  • s consists of '0' and '1'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var maxScore = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Score After Splitting a String — Problem & Solution

Maximum Score After Splitting a String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Maximum Score After Splitting a String is an easy coding problem on strings and prefix sum, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Strings, Prefix Sum
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a string s of zeros and ones, split it into two non-empty parts, left and right.

The score of a split is the number of zeros in the left part plus the number of ones in the right part. Return the maximum score.

Example 1

Input: s = "011101"
Output: 5
Explanation: Splitting after the first character gives 1 zero on the left and 4 ones on the right.

Example 2

Input: s = "00111"
Output: 5

Example 3

Input: s = "1111"
Output: 3
Explanation: The left part must be non-empty, so one 1 is always sacrificed.

Constraints

  • 2 <= s.length <= 40
  • s consists of '0' and '1'.

Hints for Maximum Score After Splitting a String

  1. Hint 1

    Count the total ones first, then sweep the split point left to right.

  2. Hint 2

    Moving the split past a 0 adds one to the left count; moving past a 1 removes one from the right count.

  3. Hint 3

    Stop before the final character — the right part must stay non-empty.

How to solve Maximum Score After Splitting a String

Count the total ones, then sweep the split point: a 0 on the left adds to the left score, a 1 moving left subtracts from the right score.

Approach

  1. rightOnes = count of '1', zeros = 0.
  2. For i from 0 to n - 2: update zeros or rightOnes for s[i], then best = max(best, zeros + rightOnes).

Why it works

Each split's score is determined by what has crossed the boundary so far, and both counts update in O(1) per step.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Stop before the last index so the right part stays non-empty.

Reference solution

Python

def maxScore(s: str) -> int:
    right_ones = s.count("1")
    zeros = 0
    best = -1
    for i in range(len(s) - 1):
        if s[i] == "0":
            zeros += 1
        else:
            right_ones -= 1
        best = max(best, zeros + right_ones)
    return best

Java

public static int maxScore(String s) {
    int ones = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '1') ones++;
    }
    int zeros = 0, best = -1, rightOnes = ones;
    for (int i = 0; i < s.length() - 1; i++) {
        if (s.charAt(i) == '0') zeros++;
        else rightOnes--;
        best = Math.max(best, zeros + rightOnes);
    }
    return best;
}

C++

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

JavaScript

var maxScore = function(s) {
    let ones = 0;
    for (let i = 0; i < s.length; i++) {
        if (s[i] === "1") ones++;
    }
    let zeros = 0, best = -1, rightOnes = ones;
    for (let i = 0; i < s.length - 1; i++) {
        if (s[i] === "0") zeros++;
        else rightOnes--;
        const score = zeros + rightOnes;
        if (score > best) best = score;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Prefix Sum