What is the main strategy for Maximum Score After Splitting a String?

The main strategy is to iterate through all split points while maintaining counts of zeros on the left and ones on the right using prefix sums.

Can this problem be solved without prefix sums?

Yes, but recomputing ones on the right for each split increases time complexity to O(n^2), which is inefficient for longer strings.

Why is it important to ensure both substrings are non-empty?

Splits that create empty substrings violate the problem constraints and would produce invalid scores.

What is the time and space complexity of the optimal solution?

Time complexity is O(n) due to a single pass over the string for prefix sums and split evaluation. Space is O(1) if prefix sums are computed inline.

Does the pattern 'String plus Prefix Sum' apply here?

Yes, this problem exemplifies the 'String plus Prefix Sum' pattern by using prefix sums to efficiently compute right-side counts in linear time.

#1422

Easy

auto_awesome前缀和

LeetCode 题解工作台

分割字符串的最大得分

给你一个由若干 0 和 1 组成的字符串 s ，请你计算并返回将该字符串分割成两个非空子字符串（即左子字符串和右子字符串）所能获得的最大得分。「分割字符串的得分」为左子字符串中 0 的数量加上右子字符串中 1 的数量。示例 1：输入： s = "011101" 输出： 5 …

字符串前缀和

题目描述

给你一个由若干 0 和 1 组成的字符串 s ，请你计算并返回将该字符串分割成两个非空子字符串（即左子字符串和右子字符串）所能获得的最大得分。

「分割字符串的得分」为左子字符串中 0 的数量加上右子字符串中 1 的数量。

示例 1：

输入：s = "011101"
输出：5 
解释：
将字符串 s 划分为两个非空子字符串的可行方案有：
左子字符串 = "0" 且 右子字符串 = "11101"，得分 = 1 + 4 = 5 
左子字符串 = "01" 且 右子字符串 = "1101"，得分 = 1 + 3 = 4 
左子字符串 = "011" 且 右子字符串 = "101"，得分 = 1 + 2 = 3 
左子字符串 = "0111" 且 右子字符串 = "01"，得分 = 1 + 1 = 2 
左子字符串 = "01110" 且 右子字符串 = "1"，得分 = 2 + 1 = 3

示例 2：

输入：s = "00111"
输出：5
解释：当 左子字符串 = "00" 且 右子字符串 = "111" 时，我们得到最大得分 = 2 + 3 = 5

示例 3：

输入：s = "1111"
输出：3

提示：

2 <= s.length <= 500
字符串 s 仅由字符 '0' 和 '1' 组成。

lightbulb

解题思路

方法一：计数

我们用两个变量 $l$ 和 $r$ 分别记录左子字符串中 $0$ 的数量和右子字符串中 $1$ 的数量。初始时 $l = 0$ ，而 $r$ 则等于字符串 $s$ 中 $1$ 的数量。

遍历字符串 $s$ 的前 $n - 1$ 个字符，对于每一个位置 $i$ ，如果 $s[i] = 0$ ，则 $l$ 自增 $1$ ，否则 $r$ 自减 $1$ 。然后我们更新答案为 $l + r$ 的最大值。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def maxScore(self, s: str) -> int:
        l, r = 0, s.count("1")
        ans = 0
        for x in s[:-1]:
            l += int(x) ^ 1
            r -= int(x)
            ans = max(ans, l + r)
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Do you consider all split points including minimal left and right substrings?
question_mark
Have you optimized the calculation of ones on the right using prefix sums?
question_mark
Can you explain why recomputing counts at every split is inefficient?

warning

常见陷阱

外企场景

error
Forgetting to handle both substrings as non-empty when iterating split points.
error
Recalculating right-side ones for each split instead of using a prefix sum.
error
Miscounting zeros in the left substring when updating the score.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute the minimum score after splitting a string with the same zero-left, one-right rule.
arrow_right_alt
Given a ternary string '0', '1', '2', maximize zeros-left plus ones-right plus twos-right.
arrow_right_alt
Allow splitting into more than two substrings and compute the maximum combined score.

help

常见问题

外企场景

继续练习

#1371 每个元音包含偶数次的最长子字符串 #1208 尽可能使字符串相等 #1177 构建回文串检测