今日题目

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

思路

按题意模拟即可。

解题方法

按题意模拟。 从后往前遍历统计 1 的数量，再从前往后遍历统计 0 的数量。 为了加速，可以先统计整个序列中 1 的总数，再通过一次遍历用减法计算剩余部分中 1 的数量。 与 2025 年 1 月 3 日的题目类似：索引 i+1 到 n 中 1 的数量 = 序列中 1 的总数 - 索引 1 到 i 中 1 的数量。

复杂度

  • 时间复杂度：$O(N)$，N 为字符串 s 的长度。

  • 空间复杂度：$O(1)$，仅使用了若干额外变量。

代码

class Solution:
    def maxScore(self, s: str) -> int:
        num1 = 0
        for ch in s:
            if ch == '1':
                num1 += 1
        now0, now1, ans = 0, 0, 0
        for ch in s[:-1]:
            if ch == '0':
                now0 += 1
            else:
                now1 += 1
            ans = max(ans, now0 + num1 - now1)

        return ans