LeetCode 1422. Maximum Score After Splitting a String Solution in Java, C++, Python & More | Explanation + Code

Description

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.

Solutions

Solution 1: 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).

PythonJavaC++GoTypeScriptRust

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 ans(code-box)

class Solution { public int maxScore(String s) { int l = 0, r = 0; int n = s.length(); for (int i = 0; i < n; ++i) { if (s.charAt(i) == '1') { ++r; } } int ans = 0; for (int i = 0; i < n - 1; ++i) { l += (s.charAt(i) - '0') ^ 1; r -= s.charAt(i) - '0'; ans = Math.max(ans, l + r); } return ans; } }(code-box)

class Solution { public: int maxScore(string s) { int l = 0, r = count(s.begin(), s.end(), '1'); int ans = 0; for (int i = 0; i < s.size() - 1; ++i) { l += (s[i] - '0') ^ 1; r -= s[i] - '0'; ans = max(ans, l + r); } return ans; } };(code-box)

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 }(code-box)

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; }(code-box)

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 } }(code-box)