Easy

题目描述

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

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

示例 1：

输入：s = "011101"
输出：5
解释：
将字符串分割成两个子字符串的所有可能方案是：
left = "0" 且 right = "11101"，得分 = 1 + 4 = 5
left = "01" 且 right = "1101"，得分 = 1 + 3 = 4
left = "011" 且 right = "101"，得分 = 1 + 2 = 3
left = "0111" 且 right = "01"，得分 = 1 + 1 = 2
left = "01110" 且 right = "1"，得分 = 2 + 1 = 3

示例 2：

输入：s = "00111"
输出：5
解释：当 left = "00" 且 right = "111" 时，我们得到最大得分 = 2 + 3 = 5

示例 3：

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

提示：

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

解题思路

这道题要求我们找到字符串的最佳分割点，使得左半部分的 0 的个数加上右半部分的 1 的个数最大。

方法一：前缀和预处理（推荐）

核心思想是预先计算出每个位置右边有多少个 1，然后遍历所有可能的分割点。

  1. 首先统计整个字符串中 1 的总数
  2. 遍历字符串（注意不能分割到最后一个位置，因为右半部分不能为空）
  3. 对于每个分割点 i：
    • 左半部分的 0 的个数通过遍历累计
    • 右半部分的 1 的个数 = 总的 1 的个数 - 当前位置及之前的 1 的个数
  4. 更新最大得分

方法二：一次遍历优化

我们可以在一次遍历中同时计算左边的 0 个数和右边的 1 个数：

  • 初始时右边有所有的 1，左边有 0 个 0
  • 遍历过程中，每遇到一个字符就更新计数器
  • 在每个可能的分割点计算得分

时间复杂度 O(n)，空间复杂度 O(1)，是最优解法。

代码实现

class Solution {
public:
    int maxScore(string s) {
        int totalOnes = 0;
        for (char c : s) {
            if (c == '1') totalOnes++;
        }
        
        int maxScore = 0;
        int leftZeros = 0;
        int leftOnes = 0;
        
        // 遍历所有可能的分割点（不包括最后一个位置）
        for (int i = 0; i < s.length() - 1; i++) {
            if (s[i] == '0') {
                leftZeros++;
            } else {
                leftOnes++;
            }
            
            int rightOnes = totalOnes - leftOnes;
            int score = leftZeros + rightOnes;
            maxScore = max(maxScore, score);
        }
        
        return maxScore;
    }
};

class Solution:
    def maxScore(self, s: str) -> int:
        total_ones = s.count('1')
        
        max_score = 0
        left_zeros = 0
        left_ones = 0
        
        # 遍历所有可能的分割点（不包括最后一个位置）
        for i in range(len(s) - 1):
            if s[i] == '0':
                left_zeros += 1
            else:
                left_ones += 1
            
            right_ones = total_ones - left_ones
            score = left_zeros + right_ones
            max_score = max(max_score, score)
        
        return max_score

public class Solution {
    public int MaxScore(string s) {
        int totalOnes = 0;
        foreach (char c in s) {
            if (c == '1') totalOnes++;
        }
        
        int maxScore = 0;
        int leftZeros = 0;
        int leftOnes = 0;
        
        // 遍历所有可能的分割点（不包括最后一个位置）
        for (int i = 0; i < s.Length - 1; i++) {
            if (s[i] == '0') {
                leftZeros++;
            } else {
                leftOnes++;
            }
            
            int rightOnes = totalOnes - leftOnes;
            int score = leftZeros + rightOnes;
            maxScore = Math.Max(maxScore, score);
        }
        
        return maxScore;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var maxScore = function(s) {
    let maxScore = 0;
    let leftZeros = 0;
    let rightOnes = 0;
    
    // Count total ones in the string
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '1') rightOnes++;
    }
    
    // Try all possible split positions (excluding the last position)
    for (let i = 0; i < s.length - 1; i++) {
        if (s[i] === '0') {
            leftZeros++;
        } else {
            rightOnes--;
        }
        maxScore = Math.max(maxScore, leftZeros + rightOnes);
    }
    
    return maxScore;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(1)

其中 n 为字符串长度。时间复杂度为 O(n) 是因为需要遍历字符串两次（第一次统计 1 的总数，第二次计算最大得分）。空间复杂度为 O(1) 因为只使用了常数个变量。