Intuition

Consider all possible ways of splitting the string s into s[0]...s[i] and s[i+1]...s[n-1], where $i \in [0, n-2]$, and $n$ is the length of s. We aim to find the split that maximizes the score.

Approach

Two-pass

• First pass
  • Count the number of '1's in the entire string (denoted as right_ones).
  • Initialize the number of '0's in the first part (denoted as left_zeros) to 0 and set the variable res (which will store the maximum score) to 0.
• Second pass
  • Iterate through s, for each index i, update right_ones and left_zeros based on the character at position i.
  • Calculate the score at each step as the sum of left_zeros and right_one.
  • Compare this score with the current res, and update res if the new score is greater.

One-pass (optimized)

The score at each split can be represnted as:

\[\begin{equation} \begin{split} score_i &= 0_{left} + 1_{right} \\ &= 0_{left} + 1_{total} - 1_{left} \\ &= 1_{total} + (0_{left} - 1_{left}) \end{split} \end{equation}\]

\(1_{total}\) is a constant. By maintaining \(0_{left}\) (denoted as left_zeros) and \(1_{left}\) (denoted as left_ones), and calculating the score dynamically as we traverse s from left to right, we can compute the maximum score in one pass.

Code

Tow-pass

• Two-pass
• One-pass

• class Solution:
      def maxScore(self, s: str) -> int:
          left_zeros = 0
          right_ones = 0
          for x in s:
              if x == "1":
                  right_ones += 1
          res = 0
          for x in s[:-1]:
              if x == "0":
                  left_zeros += 1
              else:
                  right_ones -= 1
              res = max(res, left_zeros + right_ones)
          return res
  

• class Solution:
      def maxScore(self, s: str) -> int:
          left_zeros = 0
          left_ones = 0
          total_ones = 0
          res = -inf
          for x in s[:-1]:
              if x == "0":
                  left_zeros += 1
              else:
                  left_ones += 1
              res = max(res, left_zeros - left_ones)
          total_ones = left_ones if s[-1] == '0' else left_ones + 1
          return total_ones + res
  

Complexity

• Time complexity: $O(N)$
• Space complexity: $O(1)$