Today’s problem

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

Intuition

Do what the question asks.

Approach

Do what the question asks. Iterate from the back to the front to count how many 1s, iterate from the front to the back to count how many 2s. To speed up the process, we can first count how many 1s are there in the whole sequence, then use another iteration to count the remaining 1s in the sequence by doing a subtraction. Same to the question in Jan.03.2025, the number of 1s in index i + 1 to n = the number of 1s in the sequence - the number of 1s in index 1 to i.

Complexity

• Time complexity: $O(N)$, N is the length of s.

• Space complexity: $O(1)$, only a few new variables are stored.

Code

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