【2022-08-14每日一题】1422. 分割字符串的最大得分
2022-08-14
2分钟阅读时长
2022-08-14每日一题：1422. 分割字符串的最大得分
- 难度：Easy
- 标签：字符串
给你一个由若干 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'组成。
func maxScore(s string) (ans int) {
for i := 1; i < len(s); i++ {
ans = max(ans, strings.Count(s[:i], "0")+strings.Count(s[i:], "1"))
}
return
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
复杂度分析
时间复杂度：O(n^2)
空间复杂度：O(1)
方法二：两次遍历
当 1≤i<n 时，分割点 i 将字符串 s 分割成两个非空子字符串，左子字符串的下标范围是[0,i−1]，右子字符串的下标范围是 [i,n−1]。对于 1≤i<n−1，当分割点从 i 移动到 i + 1 时，位于下标 i 处的字符 s[i] 从右子字符串中移除并添加到左子字符串中，分割字符串的得分变化如下：
- 如果 s[i]=0，则左子字符串的得分加 1，右子字符串的得分不变，因此分割字符串的得分加 1；
- 如果 s[i]=1，则左子字符串的得分不变，右子字符串的得分减 1，因此分割字符串的得分减 1。
由于最左侧的分割点是 i=1，因此首先计算i=1 处的分割字符串的得分，然后从左到右依次遍历每个分割点，遍历过程中更新分割字符串的得分，遍历结束之后即可得到分割字符串的最大得分。
func maxScore(s string) int {
// strings.Count(s[1:], "1") 相当于第一次遍历
score := int('1'-s[0]) + strings.Count(s[1:], "1")
ans := score
for _, c := range s[1 : len(s)-1] {
if c == '0' {
score++
} else {
score--
}
ans = max(ans, score)
}
return ans
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
方法三：前缀和
构建前缀和数组来记录每个前缀中 1 个个数，复杂度为 O(n)，枚举每个分割点，搭配前缀和数组计算左串中 0 的数量和右串中 1 的数量，取所有得分的最大值即是答案。
func maxScore(s string) int {
n, ans, sum := len(s), 0, make([]int, len(s)+1)
// 计算0...i之间1的个数
for i := 1; i <= n; i++ {
sum[i] += sum[i-1]
if s[i-1] == '1' {
sum[i] += 1
}
}
for i := 1; i <= n-1; i++ {
zero, one := i - sum[i], sum[n] - sum[i]
ans = max(ans, zero + one)
}
return ans
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)