Maximum Score After Splitting a String — Problem & Solution
Maximum Score After Splitting a String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Maximum Score After Splitting a String is an easy coding problem on strings and prefix sum, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Strings, Prefix Sum
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a string s of zeros and ones, split it into two non-empty parts, left and right.
The score of a split is the number of zeros in the left part plus the number of ones in the right part. Return the maximum score.
Example 1
Input: s = "011101"
Output: 5
Explanation: Splitting after the first character gives 1 zero on the left and 4 ones on the right.
Example 2
Input: s = "00111"
Output: 5
Example 3
Input: s = "1111"
Output: 3
Explanation: The left part must be non-empty, so one 1 is always sacrificed.
Constraints
2 <= s.length <= 40s consists of '0' and '1'.
Hints for Maximum Score After Splitting a String
Hint 1
Count the total ones first, then sweep the split point left to right.
Hint 2
Moving the split past a
0adds one to the left count; moving past a1removes one from the right count.Hint 3
Stop before the final character — the right part must stay non-empty.
How to solve Maximum Score After Splitting a String
Count the total ones, then sweep the split point: a 0 on the left adds to the left score, a 1 moving left subtracts from the right score.
Approach
rightOnes = count of '1',zeros = 0.- For
ifrom 0 ton - 2: updatezerosorrightOnesfors[i], thenbest = max(best, zeros + rightOnes).
Why it works
Each split's score is determined by what has crossed the boundary so far, and both counts update in O(1) per step.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Stop before the last index so the right part stays non-empty.
Reference solution
Python
def maxScore(s: str) -> int:
right_ones = s.count("1")
zeros = 0
best = -1
for i in range(len(s) - 1):
if s[i] == "0":
zeros += 1
else:
right_ones -= 1
best = max(best, zeros + right_ones)
return bestJava
public static int maxScore(String s) {
int ones = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '1') ones++;
}
int zeros = 0, best = -1, rightOnes = ones;
for (int i = 0; i < s.length() - 1; i++) {
if (s.charAt(i) == '0') zeros++;
else rightOnes--;
best = Math.max(best, zeros + rightOnes);
}
return best;
}C++
int maxScore(string s) {
int ones = 0;
for (char ch : s) {
if (ch == '1') ones++;
}
int zeros = 0, best = -1, rightOnes = ones;
for (int i = 0; i < (int) s.size() - 1; i++) {
if (s[i] == '0') zeros++;
else rightOnes--;
best = max(best, zeros + rightOnes);
}
return best;
}JavaScript
var maxScore = function(s) {
let ones = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] === "1") ones++;
}
let zeros = 0, best = -1, rightOnes = ones;
for (let i = 0; i < s.length - 1; i++) {
if (s[i] === "0") zeros++;
else rightOnes--;
const score = zeros + rightOnes;
if (score > best) best = score;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Prefix Sum