Problem

Given a string s of zeros and ones, return the maximum score after splitting the string into two non-empty substrings (i.e. left substring and right substring).

The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.

Examples

Example 1

1
2
3
4
5
6
7
8
9

Input: s = "011101"
Output: 5 
Explanation: 
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5 
left = "01" and right = "1101", score = 1 + 3 = 4 
left = "011" and right = "101", score = 1 + 2 = 3 
left = "0111" and right = "01", score = 1 + 1 = 2 
left = "01110" and right = "1", score = 2 + 1 = 3

Example 2

1
2
3

Input: s = "00111"
Output: 5
Explanation: When left = "00" and right = "111", we get the maximum score = 2 + 3 = 5

Example 3

1
2

Input: s = "1111"
Output: 3

Constraints

  • 2 <= s.length <= 500
  • The string s consists of characters '0' and '1' only.

Solution

Method 1 – Prefix Sum and Single Pass

Intuition

The key idea is to try every possible split between the left and right substrings, count zeros on the left and ones on the right, and keep track of the maximum score. We can efficiently do this by precomputing the total number of ones and then iterating through the string, updating counts as we go.

Approach

  1. Count the total number of ones in the string (total_ones).
  2. Initialize left_zeros and right_ones (initially equal to total_ones).
  3. Iterate through the string from left to right, but stop before the last character (since both substrings must be non-empty).
  • If the current character is ‘0’, increment left_zeros.
  • If the current character is ‘1’, decrement right_ones.
  • At each split, calculate the score as left_zeros + right_ones and update the maximum score.
  1. Return the maximum score found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
   int maxScore(string s) {
      int ones = 0, ans = 0, zeros = 0;
      for (char c : s) if (c == '1') ones++;
      int n = s.size();
      for (int i = 0; i < n - 1; ++i) {
        if (s[i] == '0') zeros++;
        else ones--;
        ans = max(ans, zeros + ones);
      }
      return ans;
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

type Solution struct{}

func (Solution) MaxScore(s string) int {
   ones, zeros, ans := 0, 0, 0
   for _, c := range s {
      if c == '1' {
        ones++
      }
   }
   for i := 0; i < len(s)-1; i++ {
      if s[i] == '0' {
        zeros++
      } else {
        ones--
      }
      if zeros+ones > ans {
        ans = zeros + ones
      }
   }
   return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
   public int maxScore(String s) {
      int ones = 0, zeros = 0, ans = 0;
      for (char c : s.toCharArray()) if (c == '1') ones++;
      for (int i = 0; i < s.length() - 1; i++) {
        if (s.charAt(i) == '0') zeros++;
        else ones--;
        ans = Math.max(ans, zeros + ones);
      }
      return ans;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
   fun maxScore(s: String): Int {
      var ones = s.count { it == '1' }
      var zeros = 0
      var ans = 0
      for (i in 0 until s.length - 1) {
        if (s[i] == '0') zeros++
        else ones--
        ans = maxOf(ans, zeros + ones)
      }
      return ans
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
   def maxScore(self, s: str) -> int:
      ones: int = s.count('1')
      zeros: int = 0
      ans: int = 0
      for i in range(len(s) - 1):
        if s[i] == '0':
           zeros += 1
        else:
           ones -= 1
        ans = max(ans, zeros + ones)
      return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
   pub fn max_score(s: String) -> i32 {
      let bytes = s.as_bytes();
      let mut ones = bytes.iter().filter(|&&c| c == b'1').count() as i32;
      let mut zeros = 0;
      let mut ans = 0;
      for i in 0..bytes.len() - 1 {
        if bytes[i] == b'0' {
           zeros += 1;
        } else {
           ones -= 1;
        }
        ans = ans.max(zeros + ones);
      }
      ans
   }
}

Complexity

  • ⏰ Time complexity: O(n) — Single pass through the string.
  • 🧺 Space complexity: O(1) — Only a few integer variables are used.