LeetCode 1422 题解：一次遍历的在线算法

Problem

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

给你一个由若干 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' 组成。

核心思想

$O(n)$ 单次遍历的在线贪心算法，同时解得分割线位置与最大得分。

思路

首先注意到，一个字符对于得分的贡献，完全取决于它位于分隔线的左侧还是右侧。于是我们可以发现：对于一个前缀子串 $s[0...k]$ , 其内部的最优分割方案不会受到 $s[k+1]$ 及之后字符的影响。这意味着问题具备最优子结构，我们可以先尝试求解子问题的最优解然后转移得到最优解。设想一个子问题 $s[0...k-1]$ ，我们已经得到了它的最优解(最大得分和分割线位置)。现增添一个新的字符，构成一个新问题 $s[0...k]$ , 那么这个新问题的最优解有两种来源:

最优分割点在原串 $s[0...k-1]$ 范围内: 由于新字符 $s[k]$ 添加之后，所有旧的分割方案得分都会同步变化，因此旧范围内最优分割点位置不变，只需更新得分即可。
最优分割点就是新增的位置：即 $s[k-1]$ 和 $s[k]$ 之间, 这是一个全新的候选解。

那么，新问题的最大得分就是上述两种情况中的较大者。即只需要比较原最优分割位置与新位置的得分，取最大值，即可完成状态转移。与此同时，我们可以通过维护原最优分割线到新分割线之间0和1的数量，来快速比较两个得分，并完成切换分割点时得分的更新。所以每一步，我们只需要贪心地比较新旧位置的得分并完成更新即可。

解题过程

设字符串为 $s$ ，长度为 $n$ 。定义下标范围为 $[0,i]$ 的子问题，其状态为 $S_i=(\text{score}_i,p_i,r_{0,i},r_{1,i})$ ，其中：

$\text{score}$ : 当前子串的最大得分
$p$ : 当前子串的一个最优分割点位置; $p=k$ 表示分割线位于 $s[k-1]$ 到 $s[k]$ 之间
$r_0$ : 当前子问题分割点 $p$ 右侧0的个数
$r_1$ : 当前子问题分割点 $p$ 右侧1的个数

初始状态(base case):

$S_1=(\mathbf{1}[s_0=0]+\mathbf{1}[s_1=1],1,\mathbf{1}[s_1=0],\mathbf{1}[s_1=1])$

状态转移: 从 $S_i$ 转移到 $S_{i+1}$ :

S_{i+1}= \begin{cases} \left( \begin{aligned} \text{score}_i+r_{0,i}-r_{1,i}+\mathbf{1}[s_{i+1}=1],\;& i+1,\\ \mathbf{1}[s_{i+1}=0],\;& \mathbf{1}[s_{i+1}=1] \end{aligned} \right), & r_{0,i}>r_{1,i},\\[1em] \left( \begin{aligned} \text{score}_i+\mathbf{1}[s_{i+1}=1],\;& p_i,\\ r_{0,i}+\mathbf{1}[s_{i+1}=0],\;& r_{1,i}+\mathbf{1}[s_{i+1}=1] \end{aligned} \right), & \text{otherwise}. \end{cases}

具体步骤可分解为:

初始化: $p=0$ , 左侧为0则初始1分。
遍历字符串中剩下的字符, 索引为 $i$ $i$ (在 $i=1$ $i = 1$ 的时候旧位置与新位置重合，不破坏逻辑)
1. 每次先判断 $r_0>r_1$ ，若满足则更新 $p=i$ , $\text{score}\mathrel{+}=r_0-r_1$ , 同时清空 $r_0$ , $r_1$ 。
2. 再判断若新字符为0，则 $r_0$ ++, 否则 $r_1$ ++并且 $\text{score}$ ++。

Code

class Solution {
public:
    int maxScore(string s) {

        if(s.size()<2) throw exception();

        int r0 = 0;//分割点右边的0的个数
        int r1 = 0;//分割点右边的1的个数
        int p = 1; //分割线在index几的左边

        int score = (s[0]=='0');
        for(int i=1; i<s.size(); ++i){
            if(r0 > r1){//更新分割点
                p = i;
                score += r0 - r1;
                r0 = r1 = 0;
            }

            if(s.at(i) == '0'){
                ++r0;
            }
            else{
                ++r1;
                ++score;
            }
        }
        return score;
    }
};

复杂度

时间复杂度: $O(n)$
空间复杂度: $O(1)$

虽然这只是一道简单题，但追求极致效率的过程还是蛮有趣的。在LeetCode上看到了很多题解，但是似乎没有人提到17号的这种方法，并且17号自认这个方法简单易懂效率高，遂写了份题解，分享一下~ ~~因为17号是算法小白，写得不好的地方还请大佬们轻喷orz~~