Skip to content

1422. Maximum Score After Splitting a String

SourceWeekly Contest 186 Q1DifficultyEasyRating1237

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

Thinking

\(n\le 500\) allows recounting at every split, but the score is only zeros on the left plus ones on the right.

Start with the total number of ones on the right. Moving the cut: a \(0\) increments the left, a \(1\) decrements the right. Track the maximum \(l+r\), and never cut after the last character.

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

1
2
3
4
5
6
7
8
9
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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
    }
}

Comments