EasyNo. 1422
Maximum Score After Splitting a String — LeetCode 1422 Python Solution
- Pattern
- Prefix Sum
- Topics
- String, Prefix Sum
- Reading time
- 2 min
- Source
- leetcode.com
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).
Example
- Input
- s = "011101"
- Output
- 5
- Explanation
- All possible ways of splitting s into two non-empty substrings are:
Python solution
class Solution:
def maxScore(self, s: str) -> int:
l, r = 0, s.count("1")
ans = 0
for x in s[:-1]:
l += int(x) ^ 1
r -= int(x)
ans = max(ans, l + r)
return ansComplexity
- Time
- O(n)where n is the length of the string s
- Space · auxiliary
- O(1)
Pattern: Prefix Sum
Precompute running totals once so any range query becomes a single subtraction. LeetCode 1422. Maximum Score After Splitting a String is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Prefix Sum.
The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0848 | Shifting Letters | Medium |
| 1769 | Minimum Number of Operations to Move All Balls to Each Box | Medium |
| 2381 | Shifting Letters II | Medium |
| 2391 | Minimum Amount of Time to Collect Garbage | Medium |
| 2483 | Minimum Penalty for a Shop | Medium |
| 2559 | Count Vowel Strings in Ranges | Medium |
Frequently asked questions
- How hard is LeetCode 1422. Maximum Score After Splitting a String?
LeetCode 1422. Maximum Score After Splitting a String is rated Easy on LeetCode.
- What is the time complexity of LeetCode 1422. Maximum Score After Splitting a String?
The Python solution on this page runs in O(n), where n is the length of the string s.
- What is the space complexity of LeetCode 1422. Maximum Score After Splitting a String?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 1422. Maximum Score After Splitting a String cover?
LeetCode 1422. Maximum Score After Splitting a String is tagged String and Prefix Sum on LeetCode.