Scale Engineer

Maximum Score After Splitting a String

Easy
#1315Time: 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.
Patterns
Prefix Sum
Data structures
String

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.
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;    }}

Complexity

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.

Trade-offs

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.

Solutions

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)))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem