分割字符串的最大得分

标签: 字符串 前缀和

难度: Easy

给你一个由若干 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' 组成。

Submission

运行时间: 22 ms

内存: 15.9 MB

class Solution:
    def maxScore(self, s: str) -> int:
        ans=0
        c=s.count('1')
        z=int(s[0]=='0')
        o=int(s[0]=='1')
        ans=c+z-o
        for i in s[1:-1]:
            if i=='0':
                z+=1
            else:
                o+=1
            if c-o+z>ans:
                ans=c-o+z
        return ans

Explain

首先，计算字符串中'1'的总数。然后，初始化得分（ans）为整个字符串中'1'的数量加上第一个字符如果是'0'则加1，如果是'1'则减1。这样处理后，得分反映了在第一个字符处分割字符串的情况。接着，遍历字符串的其余部分（除了最后一个字符，因为右侧子字符串不能为空），更新左侧子字符串中'0'的数量和'1'的数量。每次遍历到新的字符时，计算新的得分：整个字符串的'1'的数量减去当前左侧'1'的数量加上当前左侧'0'的数量。如果这个得分大于当前记录的最大得分，就更新最大得分。这种方法确保了每一种可能的分割都被考虑，且每次只考虑当前位置的字符，有效地更新当前的得分。

时间复杂度: O(n)

空间复杂度: O(1)

# 定义解决方案类

class Solution:
    def maxScore(self, s: str) -> int:
        ans = 0  # 初始化最大得分为0
        c = s.count('1')  # 计算字符串中'1'的总数
        z = int(s[0] == '0')  # 第一个字符如果是'0'，计数为1
        o = int(s[0] == '1')  # 第一个字符如果是'1'，计数为1
        ans = c + z - o  # 计算初始分割得分
        for i in s[1:-1]:  # 遍历除最后一个字符外的所有字符
            if i == '0':
                z += 1  # 更新左侧'0'的数量
            else:
                o += 1  # 更新左侧'1'的数量
            if c - o + z > ans:  # 如果新得分高于当前最大得分
                ans = c - o + z  # 更新最大得分
        return ans  # 返回计算得到的最大得分

Explore

在这个算法中，初始化得分的操作是为了设置第一个字符作为分割点（即左子字符串包含第一个字符，右子字符串包含其余所有字符）的初始情况。如果第一个字符是'0'，则左侧子字符串的得分应该增加1（因为'0'的得分是1），如果是'1'，则因为这个'1'已经被计入了总的'1'的数量c中，所以需要从得分中减去这个'1'，以反映它不再为右侧子字符串贡献得分。这样做可以正确地初始化得分，反映出在第一个字符处进行分割的情况。

在题解中，忽略最后一个字符是因为分割字符串必须确保左右两侧都至少有一个字符。如果包括最后一个字符在内进行遍历，那么在到达字符串末尾时，右侧子字符串将为空，这违反了题目的原则。因此，为了保证每次分割后的两个子字符串都是有效的，算法只遍历到倒数第二个字符。

在公式`c - o + z`中，`c`代表整个字符串中'1'的总数，`o`代表当前左侧子字符串中'1'的数量，`z`代表左侧子字符串中'0'的数量。公式中的`c - o`实际上是计算右侧子字符串中'1'的数量，因为整个字符串的'1'数量减去左侧的'1'数量就得到右侧的'1'数量。而`z`直接代表左侧子字符串中'0'的得分。所以，`c - o + z`表示左侧子字符串的'0'得分加上右侧子字符串的'1'得分，这是当前分割位置的总得分。

是的，在实际编码实践中，应该考虑输入字符串`s`只有一个字符的情况。这种情况下，无法进行有效的分割，因为分割后一侧必然为空，这违反了题目要求左右两侧都至少有一个字符的规定。因此，应当在代码中增加判断，如果输入字符串长度不大于1，则直接返回0或其他特定值，以处理这种边界情况。