Maximum Score After Splitting A String - Leetcode Solution

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: All possible ways of splitting s into two non-empty substrings are: left = "0" and right = "0111", score = 1 + 3 = 4 left = "00" and right = "111", score = 2 + 1 = 3 left = "001" and right = "11", score = 1 + 2 = 3 left = "0011" and right = "1", score = 2 + 1 = 3 left = "00111" and right = "", score = 3 + 0 = 3

Solution:

To solve this problem, we need to split the string into two non-empty substrings and calculate the maximum score. We can achieve this by iterating over the string s and counting the number of zeros and ones we encounter from left to right (i.e. in the prefix) and from right to left (i.e. in the suffix).

We can then split the string at each position i and calculate the score using the formula: score = number of zeros in prefix + number of ones in suffix. We can keep track of the maximum score seen so far and return it at the end.

Algorithm:

1. Initialize a variable max_score to zero.
2. Initialize two variables zeros and ones to zero.
3. Iterate over the string s: a. If the current character is '0', increment the zeros count. b. If the current character is '1', increment the ones count.
4. Iterate over the string s: a. If the current character is '0', increment the zeros count. b. If the current character is '1', increment the ones count. c. Calculate the score using the formula: score = zeros + (length of s - i - 1) - ones. d. If the score is greater than max_score, update max_score to score.
5. Return max_score.

Code:

class Solution: def maxScore(self, s: str) -> int: n = len(s) max_score = 0 zeros = 0 ones = 0 for i in range(n): if s[i] == '0': zeros += 1 else: ones += 1 for i in range(n - 1): if s[i] == '0': zeros += 1 else: ones += 1 score = zeros + (n - i - 2) - ones if score > max_score: max_score = score return max_score

Time Complexity: O(n), where n is the length of the string s.

Space Complexity: O(1).

1