Maximum Score After Splitting a String

main.md

Question

Approach

I first thought of using recursion, but it's not that deep, hehe.

Then I thought of using a two pointer approach. Here's how it goes: I first initialize two variables - one for the left and to calculate the number of 0s in the left substring as I'd traverse and the second pointer is implicit as it's the complement of the left substring.

Then, I precompute the total number of 1s, then traverse the string. In this step, I'd update the count of 0s in the left substring as I traverse from left to right. Then on the right substring, substract the counts of 1s that have been met so far from the toal numbers of 1s to get the remaining 1s.

Then calculate each score for each split. No substring must be empty so the split must happen between indices 0to len(s) - 1

Implementation

class Solution:
    def maxScore(self, s: str) -> int:
        total_ones = s.count('1')

        max_score = 0
        left_zeroes = 0
        right_ones = total_ones

        for i in range(len(s) - 1):
            if s[i] == '0':
                left_zeroes += 1
            else:
                right_ones -= 1

            max_score = max(max_score, left_zeroes + right_ones)

        return max_score

Complexities

• Time: O(n) - counting the 1 initially and traversing the string
• Space: O(1) - using a constant space