1717.md

1717. Maximum Score From Removing Substrings

Leetcode link

解题思路

本题给了我们一个字符串 s 以及两个数字 x 与 y，其中：

• x 代表当 ab 组合从字符串去除时候得到的分数
• y 代表当 ba 组合从字符串去除时候得到的分数

最后要我们求能够从给定条件下获得的最高分数

这个题目我们可以采用顺序遍历字符串的形式来做，在遍历过程中我们会遇到几种情况：

1. 遇到了字母 a
2. 遇到了字母 b
3. 遇到了其他字母

我们来分别分析一下这三种情况：

遇到字母 a

首先我们要明确的一点是，我们的希望永远优先把分数高的组合给去除掉

当我们遇到字母 a 的时候，我们要先做两个个判断：

1. 去除 ba 的得分是否比去除 ab 高：if(y > x)
2. a 前面是否有 b 可以凑成 ba

如果这两个条件成立，恭喜，我们可以把 y 的分数收入囊中了

如果这两个条件有一个不成立，那么不好意思，我们先把 a 的数量记起来，继续遍历（因为在这一轮遍历，我们只希望去除分数高的组合）

遇到字母 b

这个时候的目标与上述一致，我们的希望永远优先把分数高的组合给去除掉

只是判断条件改了：

1. 去除 ab 的得分是否比去除 ba 高：if(x > y)
2. a 前面是否有 b 可以凑成 ab

如果条件成立，把分数 x 纳入囊中

如果不成立，记下 b 的数量，继续遍历

遇到其他字母

遇到其他字母的时候，我们的目标是：把前面分数低的得分组合做一个结算

这个目标有两个问题要解决：

1. 为什么前面都是分数低的？因为我们优先把分数高的组合去除了，剩下来的 a/b 只可能是分数低的组合或者单个字母两种情况
2. 要怎么结算？我们取 a/b 中数量最少的个数去✖️低分分数

循环结束

当循环结束的时候，字符串的尾巴可能还会有剩下一些低分组合，要记得把这些低分组合用遇到其他字母的算法做一个结算

Javascript

/**
 * @param {string} s
 * @param {number} x: 'ab'
 * @param {number} y: 'ba'
 * @return {number}
 */
var maximumGain = function(s, x, y) {
    let aCount = 0;
    let bCount = 0;
    const minPoint = Math.min(x, y);
    let result = 0;

    for(let i=0;i<s.length;i++) {
        let c = s[i];
        switch(true) {
            case c > 'b':
                // 如果出现了不是 a/b 的字符，要把前面留存的 a/b 的分数算一下
                // 因为后面两个 case 的规则决定了当出现分数比较高的组合会第一时间处理掉
                // 所以这里如果有能凑成一堆的 a/b，一定是分数比较低的组合
                result += Math.min(aCount, bCount) * minPoint;
                aCount = bCount = 0;
                break;
            case c === 'a':
                // 当 y > x 且 ba 组合出现的时候，优先处理掉当前的 ba 组合（计算分数）
                if(y > x && bCount > 0) {
                    result += y;
                    bCount--;
                } else {
                    // 如果没出现，就先记着之后处理
                    aCount++;
                }
                break;
            case c === 'b':
                // 当 x > y 且 ab 组合出现的时候，优先处理掉当前的 ab 组合（计算分数）
                if(x > y && aCount > 0) {
                    result += x;
                    aCount--;
                } else {
                    // 如果没出现，就先记着之后处理
                    bCount++;
                }
                break;
        }
    }
    // 当上述循环结束的时候，有可能还会有分数少的组合在字符串末尾没有处理的情况，这里统一处理
    result += Math.min(aCount, bCount) * minPoint;
    return result;
};