# Maximum Score After Splitting a String
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-score-after-splitting-a-string)
Canonical: https://scaleengineer.com/dsa/problems/maximum-score-after-splitting-a-string
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** String
---
## 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.

**Example 1:**

**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:**

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

**Example 3:**

**Input:** s = "1111"
**Output:** 3

**Constraints:**

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

# Approaches
## Brute Force Iteration
The most straightforward approach is to simulate the splitting process for every possible position. The string can be split at any point from the first character to the second-to-last character, ensuring both left and right substrings are non-empty. For each split, we form the two substrings and manually count the zeros on the left and ones on the right to calculate the score. We keep track of the maximum score seen so far.
**Time:** O(N^2), where N is the length of the string `s`. The main loop runs N-1 times. In each iteration, creating substrings and then iterating over them to count characters takes O(N) time, resulting in a total time complexity of O(N * N) = O(N^2). · **Space:** O(N), because in each iteration of the loop, we create two new substrings. The combined length of these substrings is N, so the space required is proportional to N.
**Pros:** Simple to conceptualize and implement.; Directly follows the problem definition.
**Cons:** Inefficient due to repeated work. Counting characters in substrings within a loop leads to a quadratic time complexity.; Creating new substring objects in each iteration consumes extra memory.
### Explanation
We iterate through all possible split points. A string of length `N` has `N-1` possible split points. For each split point `i` (from 1 to N-1), we consider `s.substring(0, i)` as the left part and `s.substring(i)` as the right part.

We then iterate through the left substring to count the number of '0's and through the right substring to count the number of '1's. The sum of these two counts gives the score for the current split. We compare this score with a `maxScore` variable, updating it if the current score is higher. This process is repeated for all possible splits.

For example, if `s = "01101"`:
1. Split at `i=1`: `left="0"`, `right="1101"`. Zeros in left = 1, Ones in right = 3. Score = 4. `maxScore = 4`.
2. Split at `i=2`: `left="01"`, `right="101"`. Zeros in left = 1, Ones in right = 2. Score = 3. `maxScore` remains 4.
3. ...and so on.

```java
class Solution {
    public int maxScore(String s) {
        int maxScore = 0;
        int n = s.length();
        // Iterate through all possible split points
        for (int i = 1; i < n; i++) {
            String left = s.substring(0, i);
            String right = s.substring(i);
            
            int zerosLeft = 0;
            for (char c : left.toCharArray()) {
                if (c == '0') {
                    zerosLeft++;
                }
            }
            
            int onesRight = 0;
            for (char c : right.toCharArray()) {
                if (c == '1') {
                    onesRight++;
                }
            }
            
            int currentScore = zerosLeft + onesRight;
            maxScore = Math.max(maxScore, currentScore);
        }
        return maxScore;
    }
}
```
### Algorithm
- Initialize a variable `maxScore` to 0.
- Loop through the string with an index `i` from 1 to `length - 1`. This index `i` marks the beginning of the right substring.
- Inside the loop, for each `i`:
    - Create the left substring `s.substring(0, i)`.
    - Create the right substring `s.substring(i)`.
    - Count the number of '0's in the left substring.
    - Count the number of '1's in the right substring.
    - Sum these counts to get the `currentScore`.
    - Update `maxScore` with the maximum of `maxScore` and `currentScore`.
- After the loop finishes, return `maxScore`.

## Optimal Single Pass Approach
A more efficient approach avoids the redundant counting of the brute-force method. We can observe that as we move the split point one position to the right, the counts of zeros and ones change predictably. This allows us to calculate the score for each split in constant time after an initial setup.
**Time:** O(N), where N is the length of the string `s`. The algorithm involves two separate, non-nested loops over the string, each taking O(N) time. Thus, the total time complexity is O(N) + O(N) = O(N). · **Space:** O(1). We only use a few integer variables (`onesRight`, `zerosLeft`, `maxScore`) to store the counts, regardless of the input string size. The space used is constant.
**Pros:** Highly efficient with linear time complexity.; Constant space complexity as it only uses a few variables for counting.; Avoids expensive substring creation.
**Cons:** Slightly less intuitive than the brute-force approach as it requires reasoning about how counts change dynamically.
### Explanation
This method can be implemented in two passes over the string, resulting in a linear time complexity.

**Pass 1: Pre-computation**
First, we iterate through the entire string once to count the total number of '1's. Let's call this `onesRight` as it represents the initial count of ones in the right part of the split.

**Pass 2: Calculating Scores**
Next, we iterate through the string from left to right, from index `i = 0` to `n-2` (where `n` is the string length), simulating the split after each character. We maintain a running count of zeros in the left part (`zerosLeft`).
- Initially, `zerosLeft` is 0.
- As we iterate, if we encounter a '0' at index `i`, we increment `zerosLeft`.
- If we encounter a '1', it means this '1' is moving from the right part to the left part, so we decrement `onesRight`.
- After updating the counts for the character at index `i`, we calculate the score for the split after `i` as `zerosLeft + onesRight` and update our `maxScore`.

This way, we update the scores in O(1) time for each split point, leading to an overall O(N) solution.

```java
class Solution {
    public int maxScore(String s) {
        int n = s.length();
        int onesRight = 0;
        // First pass: count all ones. This will be the initial count for the right part.
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') {
                onesRight++;
            }
        }

        int maxScore = 0;
        int zerosLeft = 0;
        // Second pass: iterate through all possible split points
        for (int i = 0; i < n - 1; i++) {
            // Update counts based on the character at the current split boundary
            if (s.charAt(i) == '0') {
                zerosLeft++;
            } else { // s.charAt(i) == '1'
                onesRight--;
            }
            // Calculate score for the current split and update maxScore
            maxScore = Math.max(maxScore, zerosLeft + onesRight);
        }
        return maxScore;
    }
}
```
### Algorithm
- Initialize `onesRight` by counting all '1's in the string `s`.
- Initialize `zerosLeft = 0` and `maxScore = 0`.
- Loop through the string with an index `i` from 0 to `length - 2`. This loop considers the character `s.charAt(i)` as the last character of the left part.
- Inside the loop:
    - If `s.charAt(i)` is '0', increment `zerosLeft`.
    - If `s.charAt(i)` is '1', decrement `onesRight` (as this '1' is now part of the left substring).
    - Calculate the `currentScore` as `zerosLeft + onesRight`.
    - Update `maxScore` with the maximum of `maxScore` and `currentScore`.
- After the loop, return `maxScore`.

# Solutions
### Python

```python
class Solution:
    def maxScore(self, s: str) -> int: return max(
        s[: i]. count('0') + s[i:]. count('1') for i in range(1, len(s)))

```

### Java

```java
class Solution {
public
  int maxScore(String s) {
    int ans = 0;
    for (int i = 1; i < s.length(); ++i) {
      int t = 0;
      for (int j = 0; j < i; ++j) {
        if (s.charAt(j) == '0') {
          ++t;
        }
      }
      for (int j = i; j < s.length(); ++j) {
        if (s.charAt(j) == '1') {
          ++t;
        }
      }
      ans = Math.max(ans, t);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxScore(string s) {
    int ans = 0;
    for (int i = 1, n = s.size(); i < n; ++i) {
      int t = 0;
      for (int j = 0; j < i; ++j) {
        t += s[j] == '0';
      }
      for (int j = i; j < n; ++j) {
        t += s[j] == '1';
      }
      ans = max(ans, t);
    }
    return ans;
  }
};

```