💬 Discord
Sign In
NeetCode #75LC-1422EasyArrays & Hashing
← Back to All Problems

#75 · #1422 · Maximum Score After Splitting a String(分割字符串的最大得分)

📌 Problem Statement & Constraints

Given a string s of 0s and 1s, split it into two non-empty parts. The score is the number of 0s in the left part plus the number of 1s in the right part. Return the maximum score. Constraints: 2 <= s.length <= 500.

💡 Core Algorithmic Approaches

  1. Precompute the total number of ones so the right part's one-count is available in O(1).
  2. Sweep the split point from left to right, maintaining left_ones and deriving left_zeros = (i + 1) - left_ones.
  3. The right part's ones are total_ones - left_ones, so the score is left_zeros + (total_ones - left_ones).
  4. The split point only runs up to n - 2, since the right part must be non-empty.

💻 Benchmark Python3 Implementation

class Solution:
    def maxScore(self, s: str) -> int:
        total_ones = s.count("1")
        left_ones = 0
        best = 0
        for i in range(len(s) - 1):        # right part must be non-empty
            if s[i] == "1":
                left_ones += 1
            left_zeros = (i + 1) - left_ones
            best = max(best, left_zeros + (total_ones - left_ones))
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass to count the ones and one pass to evaluate the splits.
💾 Space Complexity
O(1): two counters.

⚠️ Interview Pitfalls & Follow-ups

  • Splitting at the last index: the right part must be non-empty, so the loop stops at n - 2.
  • Recounting the right part's ones each time: O(n^2). Deriving it from the total makes each step O(1).
  • Counting the left part's zeros by scanning: use the identity zeros = length - ones instead.
  • Initialising best to a negative number: the score is always non-negative, and 0 is a valid score for s = "11"... actually the score for "11" is 0 + 1 = 1, so initialising to 0 is safe because at least one split is always evaluated.