1422. 分割字符串的最大得分

🟢   🔖  字符串 前缀和  🔗 力扣 LeetCode

题目

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.

题目大意

给你一个由若干 0 和 1 组成的字符串 s ，请你计算并返回将该字符串分割成两个 非空 子字符串（即 左 子字符串和 右 子字符串）所能获得的最大得分。

「分割字符串的得分」为 左 子字符串中 0 的数量加上 右 子字符串中 1 的数量。

示例 1：

输入： s = "011101"

输出： 5

解释：

将字符串 s 划分为两个非空子字符串的可行方案有：

左子字符串 = "0" 且 右子字符串 = "11101"，得分 = 1 + 4 = 5

左子字符串 = "01" 且 右子字符串 = "1101"，得分 = 1 + 3 = 4

左子字符串 = "011" 且 右子字符串 = "101"，得分 = 1 + 2 = 3

左子字符串 = "0111" 且 右子字符串 = "01"，得分 = 1 + 1 = 2

左子字符串 = "01110" 且 右子字符串 = "1"，得分 = 2 + 1 = 3

示例 2：

输入： s = "00111"

输出： 5

解释： 当 左子字符串 = "00" 且 右子字符串 = "111" 时，我们得到最大得分 = 2 + 3 = 5

示例 3：

输入： s = "1111"

输出： 3

提示：

• 2 <= s.length <= 500
• 字符串 s 仅由字符 '0' 和 '1' 组成。

解题思路

1. 统计字符串中 1 的总数：

   • 由于划分时需要动态计算右侧 1 的数量，因此先统计 1 的总数 ones。

2. 遍历字符串进行划分：

   • 使用变量 zeros 记录左部分的 0 的数量。
   • 从左到右遍历字符串的前 s.length - 1 个字符（子字符串不能为空），动态调整 zeros 和 ones。
     • 如果字符为 1，从 ones 中减去 1（因为这个 1 进入了左部分）。
     • 如果字符为 0，将其计入 zeros。
   • 每次划分时，计算当前划分的分数 zeros + ones，更新最大值 res。

3. 返回结果：

   • 遍历结束后，res 即为最大得分。

复杂度分析

• 时间复杂度：O(n)，遍历字符串两次：第一次统计 1 的总数，第二次进行划分计算。
• 空间复杂度：O(1)，仅使用常数额外空间存储变量 ones、zeros 和 res。

代码

/**
 * @param {string} s
 * @return {number}
 */
var maxScore = function (s) {
	let ones = 0;
	for (let char of s) {
		if (char == '1') {
			ones++;
		}
	}

	let zeros = 0;
	let res = 0;

	// 遍历前 s.length - 1 个字符
	for (let i = 0; i < s.length - 1; i++) {
		if (s[i] == '1') {
			ones--;
		} else {
			zeros++;
		}
		res = Math.max(res, zeros + ones);
	}

	return res;
};