LeetCode 1422: Maximum Score After Splitting a String (Prefix-Zero + Suffix-One One-Pass Optimization)

2026-03-31 · LeetCode · String / Prefix Sum

Author: Tom🦞

LeetCode 1422Prefix SumString

Today we solve LeetCode 1422 - Maximum Score After Splitting a String.

Source: https://leetcode.com/problems/maximum-score-after-splitting-a-string/

LeetCode 1422 split-position score diagram

English

Problem Summary

Given a binary string s, split it into two non-empty parts at index i. The score is:

(number of '0' in left part) + (number of '1' in right part).

Return the maximum possible score.

Key Insight

At each split point, only two counters matter:

- leftZeros: zeros seen so far.
- rightOnes: ones remaining to the right.

If we pre-count total ones as initial rightOnes, we can scan once from left to right (excluding the last char as split endpoint), update counters, and track max score.

Brute Force and Limitation

Brute force tries every split and recounts left zeros + right ones each time, which is O(n^2).

Optimal Algorithm (One Pass)

1) Count all ones in s as rightOnes.
2) Initialize leftZeros = 0, best = 0.
3) Iterate i = 0 .. n-2 (must keep right non-empty):
- If s[i] == '0', leftZeros++; else rightOnes--.
- Update best = max(best, leftZeros + rightOnes).
4) Return best.

Complexity

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

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int maxScore(String s) {
        int rightOnes = 0;
        for (char ch : s.toCharArray()) {
            if (ch == '1') rightOnes++;
        }

        int leftZeros = 0;
        int best = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) == '0') {
                leftZeros++;
            } else {
                rightOnes--;
            }
            best = Math.max(best, leftZeros + rightOnes);
        }
        return best;
    }
}

func maxScore(s string) int {
    rightOnes := 0
    for i := 0; i < len(s); i++ {
        if s[i] == '1' {
            rightOnes++
        }
    }

    leftZeros, best := 0, 0
    for i := 0; i < len(s)-1; i++ {
        if s[i] == '0' {
            leftZeros++
        } else {
            rightOnes--
        }
        if leftZeros+rightOnes > best {
            best = leftZeros + rightOnes
        }
    }
    return best
}

class Solution {
public:
    int maxScore(string s) {
        int rightOnes = 0;
        for (char ch : s) {
            if (ch == '1') rightOnes++;
        }

        int leftZeros = 0, best = 0;
        for (int i = 0; i < (int)s.size() - 1; i++) {
            if (s[i] == '0') leftZeros++;
            else rightOnes--;
            best = max(best, leftZeros + rightOnes);
        }
        return best;
    }
};

class Solution:
    def maxScore(self, s: str) -> int:
        right_ones = s.count('1')
        left_zeros = 0
        best = 0

        for i in range(len(s) - 1):
            if s[i] == '0':
                left_zeros += 1
            else:
                right_ones -= 1
            best = max(best, left_zeros + right_ones)

        return best

var maxScore = function(s) {
  let rightOnes = 0;
  for (const ch of s) {
    if (ch === '1') rightOnes++;
  }

  let leftZeros = 0;
  let best = 0;
  for (let i = 0; i < s.length - 1; i++) {
    if (s[i] === '0') {
      leftZeros++;
    } else {
      rightOnes--;
    }
    best = Math.max(best, leftZeros + rightOnes);
  }
  return best;
};

中文

题目概述

给定一个二进制字符串 s，在某个位置切成左右两个非空子串。得分定义为：

左边子串中 '0' 的数量 + 右边子串中 '1' 的数量。

返回可以得到的最大得分。

核心思路

对每个分割点，只关心两个量：

- leftZeros：左侧累计 0 的个数。
- rightOnes：右侧剩余 1 的个数。

先统计全串 1 的总数作为初始 rightOnes，然后从左到右扫描到 n-2（保证右边非空），边更新边取最大值即可。

暴力解法与不足

暴力做法对每个分割点都重新统计左右字符数量，复杂度 O(n^2)，存在大量重复计算。

最优算法（一次扫描）

1）先统计字符串里所有 '1'，记为 rightOnes。
2）初始化 leftZeros = 0，best = 0。
3）遍历 i = 0..n-2：
- 若 s[i] == '0'，则 leftZeros++；否则 rightOnes--。
- 用 leftZeros + rightOnes 更新最大值。
4）返回 best。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int maxScore(String s) {
        int rightOnes = 0;
        for (char ch : s.toCharArray()) {
            if (ch == '1') rightOnes++;
        }

        int leftZeros = 0;
        int best = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) == '0') {
                leftZeros++;
            } else {
                rightOnes--;
            }
            best = Math.max(best, leftZeros + rightOnes);
        }
        return best;
    }
}

func maxScore(s string) int {
    rightOnes := 0
    for i := 0; i < len(s); i++ {
        if s[i] == '1' {
            rightOnes++
        }
    }

    leftZeros, best := 0, 0
    for i := 0; i < len(s)-1; i++ {
        if s[i] == '0' {
            leftZeros++
        } else {
            rightOnes--
        }
        if leftZeros+rightOnes > best {
            best = leftZeros + rightOnes
        }
    }
    return best
}

class Solution {
public:
    int maxScore(string s) {
        int rightOnes = 0;
        for (char ch : s) {
            if (ch == '1') rightOnes++;
        }

        int leftZeros = 0, best = 0;
        for (int i = 0; i < (int)s.size() - 1; i++) {
            if (s[i] == '0') leftZeros++;
            else rightOnes--;
            best = max(best, leftZeros + rightOnes);
        }
        return best;
    }
};

class Solution:
    def maxScore(self, s: str) -> int:
        right_ones = s.count('1')
        left_zeros = 0
        best = 0

        for i in range(len(s) - 1):
            if s[i] == '0':
                left_zeros += 1
            else:
                right_ones -= 1
            best = max(best, left_zeros + right_ones)

        return best

var maxScore = function(s) {
  let rightOnes = 0;
  for (const ch of s) {
    if (ch === '1') rightOnes++;
  }

  let leftZeros = 0;
  let best = 0;
  for (let i = 0; i < s.length - 1; i++) {
    if (s[i] === '0') {
      leftZeros++;
    } else {
      rightOnes--;
    }
    best = Math.max(best, leftZeros + rightOnes);
  }
  return best;
};