1422. Maximum Score After Splitting a String - Explanation

Description

You are given a string s of zeros and ones, return the maximum score after splitting the string into two non-empty substrings (i.e. left substring and right substring).

The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.

Example 1:

Input: s = "011101"

Output: 5

Explanation: All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5
left = "01" and right = "1101", score = 1 + 3 = 4
left = "011" and right = "101", score = 1 + 2 = 3
left = "0111" and right = "01", score = 1 + 1 = 2
left = "01110" and right = "1", score = 2 + 1 = 3

Example 2:

Input: s = "00111"

Output: 5

Example 3:

Input: s = "1111"

Output: 3

Constraints:

2 <= s.length <= 500
s consists of characters '0' and '1' only.

Topics

String Prefix Sum

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Prefix Sums - Precomputing cumulative counts to enable O(1) lookups for range queries
String Traversal - Iterating through a string while maintaining running counts of characters
Algebraic Optimization - Reformulating the score formula to reduce the problem to a single-pass solution

1. Brute Force

Intuition

The score at any split point is the sum of zeros in the left substring plus the sum of ones in the right substring. The simplest approach is to try every valid split position and count directly. For each split, we scan the left portion to count zeros and the right portion to count ones, then track the maximum score found.

Algorithm

Iterate through each valid split position i from index 1 to n-1 (both substrings must be non-empty).
For each split position:
- Count zeros in the left substring (indices 0 to i-1).
- Count ones in the right substring (indices i to n-1).
- Calculate the score as the sum of these two counts.
Track and return the maximum score across all split positions.

class Solution:
    def maxScore(self, s: str) -> int:
        n, res = len(s), 0
        for i in range(1, n):
            left_zero = 0
            for j in range(i):
                if s[j] == '0':
                    left_zero += 1
            right_one = 0
            for j in range(i, n):
                if s[j] == '1':
                    right_one += 1
            res = max(res, left_zero + right_one)
        return res

public class Solution {
    public int maxScore(String s) {
        int n = s.length(), res = 0;
        for (int i = 1; i < n; i++) {
            int leftZero = 0, rightOne = 0;
            for (int j = 0; j < i; j++) {
                if (s.charAt(j) == '0') {
                    leftZero++;
                }
            }
            for (int j = i; j < n; j++) {
                if (s.charAt(j) == '1') {
                    rightOne++;
                }
            }
            res = Math.max(res, leftZero + rightOne);
        }
        return res;
    }
}

class Solution {
public:
    int maxScore(string s) {
        int n = s.size(), res = 0;
        for (int i = 1; i < n; i++) {
            int leftZero = 0, rightOne = 0;
            for (int j = 0; j < i; j++) {
                if (s[j] == '0') {
                    leftZero++;
                }
            }
            for (int j = i; j < n; j++) {
                if (s[j] == '1') {
                    rightOne++;
                }
            }
            res = max(res, leftZero + rightOne);
        }
        return res;
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    maxScore(s) {
        const n = s.length;
        let res = 0;
        for (let i = 1; i < n; i++) {
            let leftZero = 0,
                rightOne = 0;
            for (let j = 0; j < i; j++) {
                if (s[j] === '0') {
                    leftZero++;
                }
            }
            for (let j = i; j < n; j++) {
                if (s[j] === '1') {
                    rightOne++;
                }
            }
            res = Math.max(res, leftZero + rightOne);
        }
        return res;
    }
}

public class Solution {
    public int MaxScore(string s) {
        int n = s.Length, res = 0;
        for (int i = 1; i < n; i++) {
            int leftZero = 0, rightOne = 0;
            for (int j = 0; j < i; j++) {
                if (s[j] == '0') leftZero++;
            }
            for (int j = i; j < n; j++) {
                if (s[j] == '1') rightOne++;
            }
            res = Math.Max(res, leftZero + rightOne);
        }
        return res;
    }
}

func maxScore(s string) int {
    n := len(s)
    res := 0
    for i := 1; i < n; i++ {
        leftZero, rightOne := 0, 0
        for j := 0; j < i; j++ {
            if s[j] == '0' {
                leftZero++
            }
        }
        for j := i; j < n; j++ {
            if s[j] == '1' {
                rightOne++
            }
        }
        if leftZero+rightOne > res {
            res = leftZero + rightOne
        }
    }
    return res
}

class Solution {
    fun maxScore(s: String): Int {
        val n = s.length
        var res = 0
        for (i in 1 until n) {
            var leftZero = 0
            var rightOne = 0
            for (j in 0 until i) {
                if (s[j] == '0') leftZero++
            }
            for (j in i until n) {
                if (s[j] == '1') rightOne++
            }
            res = maxOf(res, leftZero + rightOne)
        }
        return res
    }
}

class Solution {
    func maxScore(_ s: String) -> Int {
        let chars = Array(s)
        let n = chars.count
        var res = 0
        for i in 1..<n {
            var leftZero = 0, rightOne = 0
            for j in 0..<i {
                if chars[j] == "0" { leftZero += 1 }
            }
            for j in i..<n {
                if chars[j] == "1" { rightOne += 1 }
            }
            res = max(res, leftZero + rightOne)
        }
        return res
    }
}

impl Solution {
    pub fn max_score(s: String) -> i32 {
        let s = s.as_bytes();
        let n = s.len();
        let mut res = 0;
        for i in 1..n {
            let mut left_zero = 0;
            let mut right_one = 0;
            for j in 0..i {
                if s[j] == b'0' {
                    left_zero += 1;
                }
            }
            for j in i..n {
                if s[j] == b'1' {
                    right_one += 1;
                }
            }
            res = res.max(left_zero + right_one);
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Prefix & Suffix Arrays

Intuition

Instead of recounting zeros and ones for every split position, we can precompute cumulative counts. A prefix array stores the count of zeros up to each index, while a suffix array stores the count of ones from each index to the end. This way, evaluating any split becomes an O(1) lookup.

Algorithm

Build a prefix array left_zero where left_zero[i] holds the count of zeros from index 0 to i.
Build a suffix array right_one where right_one[i] holds the count of ones from index i to n-1.
For each valid split position i (from 1 to n-1):
- The score is left_zero[i-1] + right_one[i].
Return the maximum score found.

class Solution:
    def maxScore(self, s: str) -> int:
        n = len(s)
        left_zero = [0] * n
        right_one = [0] * n

        if s[0] == '0':
            left_zero[0] = 1
        for i in range(1, n):
            left_zero[i] = left_zero[i - 1]
            if s[i] == '0':
                left_zero[i] += 1

        if s[n - 1] == '1':
            right_one[n - 1] = 1
        for i in range(n - 2, -1, -1):
            right_one[i] = right_one[i + 1]
            if s[i] == '1':
                right_one[i] += 1

        res = 0
        for i in range(1, n):
            res = max(res, left_zero[i - 1] + right_one[i])
        return res

public class Solution {
    public int maxScore(String s) {
        int n = s.length();
        int[] leftZero = new int[n];
        int[] rightOne = new int[n];

        if (s.charAt(0) == '0') {
            leftZero[0] = 1;
        }
        for (int i = 1; i < n; i++) {
            leftZero[i] = leftZero[i - 1];
            if (s.charAt(i) == '0') {
                leftZero[i]++;
            }
        }

        if (s.charAt(n - 1) == '1') {
            rightOne[n - 1] = 1;
        }
        for (int i = n - 2; i >= 0; i--) {
            rightOne[i] = rightOne[i + 1];
            if (s.charAt(i) == '1') {
                rightOne[i]++;
            }
        }

        int res = 0;
        for (int i = 1; i < n; i++) {
            res = Math.max(res, leftZero[i - 1] + rightOne[i]);
        }
        return res;
    }
}

class Solution {
public:
    int maxScore(string s) {
        int n = s.size();
        vector<int> leftZero(n, 0), rightOne(n, 0);

        if (s[0] == '0') {
            leftZero[0] = 1;
        }
        for (int i = 1; i < n; i++) {
            leftZero[i] = leftZero[i - 1];
            if (s[i] == '0') {
                leftZero[i]++;
            }
        }

        if (s[n - 1] == '1') {
            rightOne[n - 1] = 1;
        }
        for (int i = n - 2; i >= 0; i--) {
            rightOne[i] = rightOne[i + 1];
            if (s[i] == '1') {
                rightOne[i]++;
            }
        }

        int res = 0;
        for (int i = 1; i < n; i++) {
            res = max(res, leftZero[i - 1] + rightOne[i]);
        }
        return res;
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    maxScore(s) {
        const n = s.length;
        let leftZero = new Array(n).fill(0);
        let rightOne = new Array(n).fill(0);

        if (s[0] === '0') {
            leftZero[0] = 1;
        }
        for (let i = 1; i < n; i++) {
            leftZero[i] = leftZero[i - 1];
            if (s[i] === '0') {
                leftZero[i]++;
            }
        }

        if (s[n - 1] === '1') {
            rightOne[n - 1] = 1;
        }
        for (let i = n - 2; i >= 0; i--) {
            rightOne[i] = rightOne[i + 1];
            if (s[i] === '1') {
                rightOne[i]++;
            }
        }

        let res = 0;
        for (let i = 1; i < n; i++) {
            res = Math.max(res, leftZero[i - 1] + rightOne[i]);
        }
        return res;
    }
}

public class Solution {
    public int MaxScore(string s) {
        int n = s.Length;
        int[] leftZero = new int[n];
        int[] rightOne = new int[n];

        if (s[0] == '0') leftZero[0] = 1;
        for (int i = 1; i < n; i++) {
            leftZero[i] = leftZero[i - 1];
            if (s[i] == '0') leftZero[i]++;
        }

        if (s[n - 1] == '1') rightOne[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            rightOne[i] = rightOne[i + 1];
            if (s[i] == '1') rightOne[i]++;
        }

        int res = 0;
        for (int i = 1; i < n; i++) {
            res = Math.Max(res, leftZero[i - 1] + rightOne[i]);
        }
        return res;
    }
}

func maxScore(s string) int {
    n := len(s)
    leftZero := make([]int, n)
    rightOne := make([]int, n)

    if s[0] == '0' {
        leftZero[0] = 1
    }
    for i := 1; i < n; i++ {
        leftZero[i] = leftZero[i-1]
        if s[i] == '0' {
            leftZero[i]++
        }
    }

    if s[n-1] == '1' {
        rightOne[n-1] = 1
    }
    for i := n - 2; i >= 0; i-- {
        rightOne[i] = rightOne[i+1]
        if s[i] == '1' {
            rightOne[i]++
        }
    }

    res := 0
    for i := 1; i < n; i++ {
        if leftZero[i-1]+rightOne[i] > res {
            res = leftZero[i-1] + rightOne[i]
        }
    }
    return res
}

class Solution {
    fun maxScore(s: String): Int {
        val n = s.length
        val leftZero = IntArray(n)
        val rightOne = IntArray(n)

        if (s[0] == '0') leftZero[0] = 1
        for (i in 1 until n) {
            leftZero[i] = leftZero[i - 1]
            if (s[i] == '0') leftZero[i]++
        }

        if (s[n - 1] == '1') rightOne[n - 1] = 1
        for (i in n - 2 downTo 0) {
            rightOne[i] = rightOne[i + 1]
            if (s[i] == '1') rightOne[i]++
        }

        var res = 0
        for (i in 1 until n) {
            res = maxOf(res, leftZero[i - 1] + rightOne[i])
        }
        return res
    }
}

class Solution {
    func maxScore(_ s: String) -> Int {
        let chars = Array(s)
        let n = chars.count
        var leftZero = [Int](repeating: 0, count: n)
        var rightOne = [Int](repeating: 0, count: n)

        if chars[0] == "0" { leftZero[0] = 1 }
        for i in 1..<n {
            leftZero[i] = leftZero[i - 1]
            if chars[i] == "0" { leftZero[i] += 1 }
        }

        if chars[n - 1] == "1" { rightOne[n - 1] = 1 }
        for i in stride(from: n - 2, through: 0, by: -1) {
            rightOne[i] = rightOne[i + 1]
            if chars[i] == "1" { rightOne[i] += 1 }
        }

        var res = 0
        for i in 1..<n {
            res = max(res, leftZero[i - 1] + rightOne[i])
        }
        return res
    }
}

impl Solution {
    pub fn max_score(s: String) -> i32 {
        let s = s.as_bytes();
        let n = s.len();
        let mut left_zero = vec![0i32; n];
        let mut right_one = vec![0i32; n];

        if s[0] == b'0' {
            left_zero[0] = 1;
        }
        for i in 1..n {
            left_zero[i] = left_zero[i - 1];
            if s[i] == b'0' {
                left_zero[i] += 1;
            }
        }

        if s[n - 1] == b'1' {
            right_one[n - 1] = 1;
        }
        for i in (0..n - 1).rev() {
            right_one[i] = right_one[i + 1];
            if s[i] == b'1' {
                right_one[i] += 1;
            }
        }

        let mut res = 0;
        for i in 1..n {
            res = res.max(left_zero[i - 1] + right_one[i]);
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Iteration (Two Pass)

Intuition

We can avoid storing full arrays by maintaining running counts. First, count all ones in the string. Then iterate through the string, incrementing zeros and decrementing ones as we move the split point. At each position, the current counts represent exactly what we need for the score calculation.

Algorithm

Count the total number of ones in the string.
Initialize zero = 0 to track zeros seen so far.
Iterate from index 0 to n-2 (last valid split position):
- If the current character is '0', increment zero.
- Otherwise, decrement one (this one moves from right to left portion).
- Update the result with zero + one.
Return the maximum score.

class Solution:
    def maxScore(self, s: str) -> int:
        zero = 0
        one = s.count('1')
        res = 0

        for i in range(len(s) - 1):
            if s[i] == '0':
                zero += 1
            else:
                one -= 1
            res = max(res, zero + one)

        return res

public class Solution {
    public int maxScore(String s) {
        int zero = 0, one = 0, res = 0;

        for (char c : s.toCharArray()) {
            if (c == '1') {
                one++;
            }
        }

        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) == '0') {
                zero++;
            } else {
                one--;
            }
            res = Math.max(res, zero + one);
        }

        return res;
    }
}

class Solution {
public:
    int maxScore(string s) {
        int zero = 0, one = 0, res = 0;

        for (char c : s) {
            if (c == '1') {
                one++;
            }
        }

        for (int i = 0; i < s.size() - 1; i++) {
            if (s[i] == '0') {
                zero++;
            } else {
                one--;
            }
            res = max(res, zero + one);
        }

        return res;
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    maxScore(s) {
        let zero = 0,
            one = 0,
            res = 0;

        for (const c of s) {
            if (c === '1') {
                one++;
            }
        }

        for (let i = 0; i < s.length - 1; i++) {
            if (s[i] === '0') {
                zero++;
            } else {
                one--;
            }
            res = Math.max(res, zero + one);
        }

        return res;
    }
}

public class Solution {
    public int MaxScore(string s) {
        int zero = 0, one = 0, res = 0;

        foreach (char c in s) {
            if (c == '1') one++;
        }

        for (int i = 0; i < s.Length - 1; i++) {
            if (s[i] == '0') zero++;
            else one--;
            res = Math.Max(res, zero + one);
        }

        return res;
    }
}

class Solution {
    fun maxScore(s: String): Int {
        var zero = 0
        var one = s.count { it == '1' }
        var res = 0

        for (i in 0 until s.length - 1) {
            if (s[i] == '0') zero++
            else one--
            res = maxOf(res, zero + one)
        }

        return res
    }
}

class Solution {
    func maxScore(_ s: String) -> Int {
        let chars = Array(s)
        var zero = 0
        var one = chars.filter { $0 == "1" }.count
        var res = 0

        for i in 0..<(chars.count - 1) {
            if chars[i] == "0" {
                zero += 1
            } else {
                one -= 1
            }
            res = max(res, zero + one)
        }

        return res
    }
}

impl Solution {
    pub fn max_score(s: String) -> i32 {
        let s = s.as_bytes();
        let mut zero = 0i32;
        let mut one = s.iter().filter(|&&c| c == b'1').count() as i32;
        let mut res = 0;

        for i in 0..s.len() - 1 {
            if s[i] == b'0' {
                zero += 1;
            } else {
                one -= 1;
            }
            res = res.max(zero + one);
        }
        res
    }
}

Time & Space Complexity

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

4. Iteration (One Pass)

Intuition

We can derive a single-pass solution using algebra. The score at position i equals left_zeros + right_ones. Since right_ones = total_ones - left_ones, the score becomes left_zeros + total_ones - left_ones, or equivalently total_ones + (left_zeros - left_ones). Since total_ones is constant, we only need to maximize (left_zeros - left_ones) while iterating, then add the total ones at the end.

Algorithm

Process the first character to initialize zeros and ones counters.
Iterate from index 1 to n-1:
- Update the maximum of (zeros - ones) before processing the current character.
- Update counters based on whether the current character is '0' or '1'.
Return result + ones (where ones now contains the total count).

class Solution:
    def maxScore(self, s: str) -> int:
        # res = Max of all (left_zeros + right_ones)
        # res = Max of all (left_zeros + (total_ones - left_ones))
        # res = total_ones (constant) + Max of all (left_zeros - left_ones)

        zeros = 0
        ones = 0

        if s[0] == '0':
            zeros += 1
        else:
            ones += 1

        res = float('-inf')
        for i in range(1, len(s)):
            res = max(res, zeros - ones)
            if s[i] == '0':
                zeros += 1
            else:
                ones += 1

        return res + ones

public class Solution {
    public int maxScore(String s) {
        // res = Max of all (leftZeros + rightOnes)
        // res = Max of all (leftZeros + (totalOnes - leftOnes))
        // res = totalOnes (constant) + Max of all (leftZeros - leftOnes)

        int zeros = 0, ones = 0, res = Integer.MIN_VALUE;

        if (s.charAt(0) == '0') {
            zeros++;
        } else {
            ones++;
        }

        for (int i = 1; i < s.length(); i++) {
            res = Math.max(res, zeros - ones);
            if (s.charAt(i) == '0') {
                zeros++;
            } else {
                ones++;
            }
        }

        return res + ones;
    }
}

class Solution {
public:
    int maxScore(string s) {
        // res = Max of all (leftZeros + rightOnes)
        // res = Max of all (leftZeros + (totalOnes - leftOnes))
        // res = totalOnes (constant) + Max of all (leftZeros - leftOnes)

        int zeros = 0, ones = 0, res = INT_MIN;

        if (s[0] == '0') {
            zeros++;
        } else {
            ones++;
        }

        for (int i = 1; i < s.size(); i++) {
            res = max(res, zeros - ones);
            if (s[i] == '0') {
                zeros++;
            } else {
                ones++;
            }
        }

        return res + ones;
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    maxScore(s) {
        // res = Max of all (leftZeros + rightOnes)
        // res = Max of all (leftZeros + (totalOnes - leftOnes))
        // res = totalOnes (constant) + Max of all (leftZeros - leftOnes)

        let zeros = 0,
            ones = 0,
            res = -Infinity;

        if (s[0] === '0') {
            zeros++;
        } else {
            ones++;
        }

        for (let i = 1; i < s.length; i++) {
            res = Math.max(res, zeros - ones);
            if (s[i] === '0') {
                zeros++;
            } else {
                ones++;
            }
        }

        return res + ones;
    }
}

public class Solution {
    public int MaxScore(string s) {
        int zeros = 0, ones = 0, res = int.MinValue;

        if (s[0] == '0') zeros++;
        else ones++;

        for (int i = 1; i < s.Length; i++) {
            res = Math.Max(res, zeros - ones);
            if (s[i] == '0') zeros++;
            else ones++;
        }

        return res + ones;
    }
}

func maxScore(s string) int {
    zeros, ones := 0, 0
    res := -1 << 31

    if s[0] == '0' {
        zeros++
    } else {
        ones++
    }

    for i := 1; i < len(s); i++ {
        if zeros-ones > res {
            res = zeros - ones
        }
        if s[i] == '0' {
            zeros++
        } else {
            ones++
        }
    }

    return res + ones
}

class Solution {
    fun maxScore(s: String): Int {
        var zeros = 0
        var ones = 0
        var res = Int.MIN_VALUE

        if (s[0] == '0') zeros++ else ones++

        for (i in 1 until s.length) {
            res = maxOf(res, zeros - ones)
            if (s[i] == '0') zeros++ else ones++
        }

        return res + ones
    }
}

class Solution {
    func maxScore(_ s: String) -> Int {
        let chars = Array(s)
        var zeros = 0, ones = 0
        var res = Int.min

        if chars[0] == "0" { zeros += 1 } else { ones += 1 }

        for i in 1..<chars.count {
            res = max(res, zeros - ones)
            if chars[i] == "0" { zeros += 1 } else { ones += 1 }
        }

        return res + ones
    }
}

impl Solution {
    pub fn max_score(s: String) -> i32 {
        let s = s.as_bytes();
        let mut zeros = 0i32;
        let mut ones = 0i32;
        let mut res = i32::MIN;

        if s[0] == b'0' {
            zeros += 1;
        } else {
            ones += 1;
        }

        for i in 1..s.len() {
            res = res.max(zeros - ones);
            if s[i] == b'0' {
                zeros += 1;
            } else {
                ones += 1;
            }
        }

        res + ones
    }
}

Time & Space Complexity

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

Common Pitfalls

Allowing Empty Substrings

The problem requires both left and right substrings to be non-empty. Splitting at index 0 (empty left) or index n (empty right) is invalid. The loop should iterate from index 1 to n-1, not from 0 to n. Forgetting this constraint leads to incorrect boundary cases.

Counting Characters in the Wrong Substring

When computing the score, zeros should be counted in the left substring only, and ones should be counted in the right substring only. A common mistake is counting ones on the left or zeros on the right, which inverts the logic and produces wrong results.