图解LeetCode——1422. 分割字符串的最大得分（难度：简单）

一、题目

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

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

二、示例

2.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.2> 示例 2：

【输入】s = "00111"
【输出】5
【解释】当 左子字符串 = "00" 且 右子字符串 = "111" 时，我们得到最大得分 = 2 + 3 = 5

2.3> 示例 3：

【输入】s = "1111"
【输出】3

提示：

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

三、解题思路

根据题意，我们可以比较直观的想到一种解题思路。就是既然是要计算分隔后字符串的总和，那么我们就把多种分隔后的字符串全都拆分出来，然后对结果进行计算，将最大值返回即可。

那么我们可以采用双层for循环进行遍历，即，最外层循环用于构建左子字符串，内层循环用于构建右子字符串。比如：以s = "011101"为例，外层循环i指向第一个元素“0”的时候，那么此时左子字符串就等于“0”；内层循环j从i+1的位置开始遍历，得到右子字符串就等于“11101”；然后外层循环i指向第二个元素"1"，此时左子字符串就累加到“01”；内层循环j从i+1的位置开始遍历，得到右子字符串就等于“1101”，以此类推；

这种计算方式思路很清晰直观，但是，大家不免发现，由于采用了双层的for循环，所以它的执行效率是比较低的，而且我们也发现，每次内部循环遍历的时候，会出现高位被多次的重复遍历的情况，那么，我们有什么更高效的处理方式吗？

从题目中的描述，我们可以知道整个字符串中，就是由“0”或者“1”来组成的。那么在左侧字符串中，“0”算作1分，“1”算作0分；而在右侧字符串中，正好与其相反，那就是“0”算作0分，“1”算作1分；既然是这样，那么我们其实就可以首先创建两个变量，用于统计左侧字符串得分——leftSum和右侧字符串得分——rightSum。现在我们假设左子串只包含数组中第一个元素，而其他的都是右子串，然后我们遍历右子串中的每一位元素的时候，依次的将其加入到左子串中，那么针对于leftSum&rightSum数值的变化，就有了如下表格中的计算方式：

那么，我们可以先遍历一下数组，让左子串只包含index=0的这个元素，其他的都是右子串。然后再依次的将index=1，index=2，index=3……“划分”给左子串，并在每次划分的操作中，计算当前的最大值。当遍历完毕后，将其作为结果返回。为了更清晰的描述算法思路，我们以s = "011101"为例，在第一次遍历的时候，我们默认左子串就是s[0]，那么leftSum等于0，右子串就是s[1]~s[5]，那么rightSum等于4；如下图所示：

我们依次将s[1]，s[2]，s[3]，s[4]划分给左子串，并计算leftSum和rightSum。那么再每次划分后，我们都可以通过leftSum + rightSum获得总分，最后将最大的总分作为结果返回即可。下面是具体的操作流程，如下图所示：

上述就是这道题的解题思路，具体的代码实现，请参照：4.1> 实现1：

四、代码实现

4.1> 实现1：

class Solution {
    public int maxScore(String s) {
        char[] sArray = s.toCharArray();
        int rightSum = 0; 
        int leftSum = sArray[0] == '0' ? 1 : 0;
        for (int i = 1; i < sArray.length; i++) {
            if (sArray[i] == '1') rightSum++;
        }
 
        int totalSum = leftSum + rightSum;
        int result = totalSum;
        for (int i = 1; i < sArray.length - 1; i++) {
            result = Math.max(result, sArray[i] == '0' ? ++totalSum : --totalSum);
        }
        return result;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」