Maximum Score After Splitting a String solution and explanation
Google
9 more videos on this problem
Maximum Score After Splitting a String - Leetcode 1422 - PythonNeetCodeIO · 6:37 · 14K views
Maximum Score After Splitting a String | 3 Approaches | Leetcode 1422codestorywithMIK · 23:02 · 9K views
Maximum Score After Splitting a String - Leetcode 1422 - PythonNeetCodeIO · 8:01 · 7K views
1422. Maximum Score After Splitting a String | 4 ways | One PassAryan Mittal · 14:05 · 2K views
How to Solve "1422 Maximum Score After Splitting a String" on LeetCode? - JavascriptBecoming A Better Dev (with David) · 7:03 · 572 views
Maximum Score After Splitting a String - LeetCode 1422 - PythonAlpha-Code · 10:26 · 111 views
1422. Maximum Score After Splitting a String | Leetcode | December Daily Challenge 2023 |Code & Coffee · 9:19 · 70 views
FIND Maximum Score After Splitting a String - Leetcode 1422Lit Code · 6:11 · 66 views
LeetCode 1422: Maximum Score After Splitting a String | Efficient Java Solution Explainedinflucoder · 3:01 · 38 views
LeetCode 1422 | Maximum Score After Splitting a StringAlgoDaily · 11:09 · 34 views
The 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
sconsists of characters'0'and'1'only.
Approach overview
Problem Overview: You get a binary string s. Split it into two non-empty parts. The score equals the number of 0s in the left substring plus the number of 1s in the right substring. Your task is to find the split position that produces the maximum score.
The brute idea is simple: try every possible split and count zeros and ones on each side. But repeated counting leads to unnecessary work. The key insight is that the score can be computed incrementally if you track counts using prefix sum style preprocessing or by updating the score during a single scan.
Approach 1: Prefix Sum Approach (O(n) time, O(n) space)
Precompute counts so each split can be evaluated in constant time. Build a prefix array where prefixZero[i] stores the number of zeros from index 0 to i. Similarly track the total number of ones or compute a suffix-style value for ones on the right. For every split position i (between i and i+1), the score becomes prefixZero[i] + (totalOnes - onesPrefix[i]). Iterate through all valid split points and keep the maximum. This method uses the classic prefix sum technique and works well when you want clear precomputation and constant-time queries for each position in a string. Time complexity is O(n) because the string is scanned a few times, and space complexity is O(n) for the prefix arrays.
Approach 2: Single Pass Score Calculation (O(n) time, O(1) space)
The optimal approach avoids extra arrays. First count the total number of ones in the entire string. That represents the initial potential contribution of the right side. Then iterate from left to right, stopping before the last character so the right substring remains non-empty. When you encounter a 0, the left score increases by one. When you encounter a 1, the right side loses one because that 1 moves to the left partition. At each position compute currentScore = zerosLeft + onesRight and update the maximum. This technique effectively simulates all splits while maintaining running counts. Time complexity is O(n) and space complexity is O(1), making it the most efficient approach for large inputs.
Recommended for interviews: Start by explaining the idea of evaluating every split and how repeated counting would be inefficient. Then move to the prefix-sum reasoning to show how preprocessing removes redundant work. Finally present the single-pass method. Interviewers usually expect the O(n), O(1) solution because it demonstrates that you can transform prefix counting logic into an in-place running calculation.
Approach 1: Prefix Sum Approach
This approach involves calculating the cumulative sum of zeros from the start up to each point, and ones from the end at each point. For each possible split, compute the score using these pre-computed sums and track the maximum score.
def max_score(s: str) -> int:
total_ones = s.count('1')
left_zeros = 0
right_ones = total_ones
max_score = 0
for i in range(len(s) - 1):
if s[i] == '0':
left_zeros += 1
else:
right_ones -= 1
max_score = max(max_score, left_zeros + right_ones)
return max_score
print(max_score("011101")) # Output: 5
print(max_score("00111")) # Output: 5
print(max_score("1111")) # Output: 3public class Main {
public static int maxScore(String s) {
int totalOnes = 0, leftZeros = 0, maxScore = 0;
for (char ch : s.toCharArray()) {
if (ch == '1') totalOnes++;
}
int rightOnes = totalOnes;
for (int i = 0; i < s.length() - 1; i++) {
if (s.charAt(i) == '0') leftZeros++;
else rightOnes--;
maxScore = Math.max(maxScore, leftZeros + rightOnes);
}
return maxScore;
}
public static void main(String[] args) {
System.out.println(maxScore("011101")); // Output: 5
System.out.println(maxScore("00111")); // Output: 5
System.out.println(maxScore("1111")); // Output: 3
}
}#include <iostream>
#include <string>
using namespace std;
int maxScore(string s) {
int totalOnes = 0, leftZeros = 0, maxScore = 0;
for (const char& ch : s) {
if (ch == '1') totalOnes++;
}
int rightOnes = totalOnes;
for (size_t i = 0; i < s.length() - 1; ++i) {
if (s[i] == '0') leftZeros++;
else rightOnes--;
int score = leftZeros + rightOnes;
if (score > maxScore) maxScore = score;
}
return maxScore;
}
int main() {
cout << maxScore("011101") << endl; // Output: 5
cout << maxScore("00111") << endl; // Output: 5
cout << maxScore("1111") << endl; // Output: 3
return 0;
}function maxScore(s) {
let totalOnes = 0, leftZeros = 0, maxScore = 0;
for (let ch of s) {
if (ch === '1') totalOnes++;
}
let rightOnes = totalOnes;
for (let i = 0; i < s.length - 1; i++) {
if (s[i] === '0') leftZeros++;
else rightOnes--;
maxScore = Math.max(maxScore, leftZeros + rightOnes);
}
return maxScore;
}
console.log(maxScore("011101")); // Output: 5
console.log(maxScore("00111")); // Output: 5
console.log(maxScore("1111")); // Output: 3#include <stdio.h>
#include <string.h>
int maxScore(char * s) {
int n = strlen(s);
int totalOnes = 0, leftZeros = 0, maxScore = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '1') totalOnes++;
}
int rightOnes = totalOnes;
for (int i = 0; i < n - 1; i++) {
if (s[i] == '0') leftZeros++;
else rightOnes--;
int score = leftZeros + rightOnes;
if (score > maxScore) maxScore = score;
}
return maxScore;
}
int main() {
printf("%d\n", maxScore("011101")); // should output 5
printf("%d\n", maxScore("00111")); // should output 5
printf("%d\n", maxScore("1111")); // should output 3
return 0;
}using System;
class Program {
public static int MaxScore(string s) {
int totalOnes = 0, leftZeros = 0, maxScore = 0;
foreach (char ch in s) {
if (ch == '1') totalOnes++;
}
int rightOnes = totalOnes;
for (int i = 0; i < s.Length - 1; i++) {
if (s[i] == '0') leftZeros++;
else rightOnes--;
maxScore = Math.Max(maxScore, leftZeros + rightOnes);
}
return maxScore;
}
static void Main(string[] args) {
Console.WriteLine(MaxScore("011101")); // Output: 5
Console.WriteLine(MaxScore("00111")); // Output: 5
Console.WriteLine(MaxScore("1111")); // Output: 3
}
}The function evaluates scores at each possible split within the string by leveraging the count of zeros in the left substring and ones in the right substring. The approach efficiently computes scores by adjusting counts incrementally.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 2: Single Pass Score Calculation
This approach derives the solution in a single pass by calculating the score dynamically using prefix sum techniques. At each character, it updates the possible maximum score by subtracting a prefix count incrementally.
def max_score_single_pass(s: str) -> int:
left_zeros = 0
right_ones = s.count('1')
max_score = 0
for i in range(len(s) - 1):
if s[i] == '0':
left_zeros += 1
else:
right_ones -= 1
max_score = max(max_score, left_zeros + right_ones)
return max_score
print(max_score_single_pass("011101")) # Output: 5
print(max_score_single_pass("00111")) # Output: 5
print(max_score_single_pass("1111")) # Output: 3public class MainSinglePass {
public static int maxScoreSinglePass(String s) {
int leftZeros = 0, rightOnes = 0, maxScore = 0;
for (char ch : s.toCharArray()) {
if (ch == '1') rightOnes++;
}
for (int i = 0; i < s.length() - 1; i++) {
if (s.charAt(i) == '0') leftZeros++;
else rightOnes--;
maxScore = Math.max(maxScore, leftZeros + rightOnes);
}
return maxScore;
}
public static void main(String[] args) {
System.out.println(maxScoreSinglePass("011101")); // Output: 5
System.out.println(maxScoreSinglePass("00111")); // Output: 5
System.out.println(maxScoreSinglePass("1111")); // Output: 3
}
}#include <iostream>
#include <string>
using namespace std;
int maxScoreSinglePass(string s) {
int leftZeros = 0, rightOnes = 0, maxScore = 0;
for (char ch : s) {
if (ch == '1') rightOnes++;
}
for (size_t i = 0; i < s.length() - 1; ++i) {
if (s[i] == '0') leftZeros++;
else rightOnes--;
maxScore = max(maxScore, leftZeros + rightOnes);
}
return maxScore;
}
int main() {
cout << maxScoreSinglePass("011101") << endl; // Output: 5
cout << maxScoreSinglePass("00111") << endl; // Output: 5
cout << maxScoreSinglePass("1111") << endl; // Output: 3
return 0;
}function maxScoreSinglePass(s) {
let leftZeros = 0, rightOnes = 0, maxScore = 0;
for (let ch of s) {
if (ch === '1') rightOnes++;
}
for (let i = 0; i < s.length - 1; i++) {
if (s[i] === '0') leftZeros++;
else rightOnes--;
maxScore = Math.max(maxScore, leftZeros + rightOnes);
}
return maxScore;
}
console.log(maxScoreSinglePass("011101")); // Output: 5
console.log(maxScoreSinglePass("00111")); // Output: 5
console.log(maxScoreSinglePass("1111")); // Output: 3#include <stdio.h>
#include <string.h>
int maxScoreSinglePass(char * s) {
int leftZeros = 0, rightOnes = 0, maxScore = 0;
int n = strlen(s);
for (int i = 0; i < n; i++) {
if (s[i] == '1') rightOnes++;
}
for (int i = 0; i < n - 1; i++) {
if (s[i] == '0') leftZeros++;
else rightOnes--;
int score = leftZeros + rightOnes;
if (score > maxScore) maxScore = score;
}
return maxScore;
}
int main() {
printf("%d\n", maxScoreSinglePass("011101")); // should output 5
printf("%d\n", maxScoreSinglePass("00111")); // should output 5
printf("%d\n", maxScoreSinglePass("1111")); // should output 3
return 0;
}using System;
class ProgramSinglePass {
public static int MaxScoreSinglePass(string s) {
int leftZeros = 0, rightOnes = 0, maxScore = 0;
foreach (char ch in s) {
if (ch == '1') rightOnes++;
}
for (int i = 0; i < s.Length - 1; i++) {
if (s[i] == '0') leftZeros++;
else rightOnes--;
maxScore = Math.Max(maxScore, leftZeros + rightOnes);
}
return maxScore;
}
static void Main(string[] args) {
Console.WriteLine(MaxScoreSinglePass("011101")); // Output: 5
Console.WriteLine(MaxScoreSinglePass("00111")); // Output: 5
Console.WriteLine(MaxScoreSinglePass("1111")); // Output: 3
}
}This Python function determines the maximum split score by leveraging a single pass through the string, updating the score dynamically based on left and right substring evaluations.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 3: Counting
We use two variables l and r to record the number of 0s in the left substring and the number of 1s in the right substring, respectively. Initially, l = 0, and r is equal to the number of 1s in the string s.
We traverse the first n - 1 characters of the string s. For each position i, if s[i] = 0, then l is incremented by 1; otherwise, r is decremented by 1. Then we update the answer to be the maximum value of l + r.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
function maxScore(s: string): number {
let [l, r] = [0, 0];
for (const c of s) {
r += c === '1' ? 1 : 0;
}
let ans = 0;
for (let i = 0; i < s.length - 1; ++i) {
if (s[i] === '0') {
++l;
} else {
--r;
}
ans = Math.max(ans, l + r);
}
return ans;
}func maxScore(s string) (ans int) {
l, r := 0, strings.Count(s, "1")
for _, c := range s[:len(s)-1] {
if c == '0' {
l++
} else {
r--
}
ans = max(ans, l+r)
}
return
}impl Solution {
pub fn max_score(s: String) -> i32 {
let mut l = 0;
let mut r = s.bytes().filter(|&b| b == b'1').count() as i32;
let mut ans = 0;
let cs = s.as_bytes();
for i in 0..s.len() - 1 {
l += ((cs[i] - b'0') ^ 1) as i32;
r -= (cs[i] - b'0') as i32;
ans = ans.max(l + r);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix Sum Approach | Time Complexity: O(n). |
| Single Pass Score Calculation | Time Complexity: O(n). |
| Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Sum Approach | O(n) | O(n) | Useful when demonstrating prefix-sum logic or when multiple range queries are needed. |
| Single Pass Score Calculation | O(n) | O(1) | Best choice for interviews and production due to constant space and a single traversal. |
Frequently asked questions
Is Maximum Score After Splitting a String easy or hard?
Maximum Score After Splitting a String is categorized as an Easy problem on LeetCode with an acceptance rate around 65%. The challenge focuses on recognizing that prefix counting or a running score can evaluate every split efficiently.
Maximum Score After Splitting a String Python/Java solution
Both Python and Java implementations follow the same idea: count total ones, iterate through the string until the second-to-last character, update zerosLeft and onesRight, and track the maximum score. The algorithm is linear O(n) and uses constant extra memory.
How to solve Maximum Score After Splitting a String in O(n)?
Count the total number of ones in the string. Traverse from left to right while tracking zeros seen so far and decreasing the count of ones remaining on the right when encountering a '1'. At each split position compute zerosLeft + onesRight and keep the maximum score.
What is the best approach for Maximum Score After Splitting a String?
The best approach is a single-pass scan that maintains the number of zeros on the left and remaining ones on the right. Start by counting total ones in the string, then iterate once while updating the score at each split position. This method runs in O(n) time and O(1) space, which is optimal.
Is Maximum Score After Splitting a String asked at Google/Amazon/Meta?
This problem is a common easy-level interview question used to evaluate string traversal and prefix counting skills. Variations of prefix sum and running-count problems appear frequently in interviews at companies like Amazon, Google, and Meta.
What data structure is used in Maximum Score After Splitting a String?
The solution primarily relies on simple counters and optional prefix sum arrays. No complex data structures are required—just integer variables to track zeros on the left and ones remaining on the right while scanning the string.
What is the time complexity of Maximum Score After Splitting a String?
The optimal solution runs in O(n) time where n is the length of the binary string. The algorithm scans the string once to count ones and once to evaluate split positions (or does both in one pass). Space complexity can be O(1) with the single-pass method or O(n) with a prefix sum array.