删除子字符串的最大得分(竞赛题)

给你一个字符串 s 和两个整数 x 和 y 。你可以执行下面两种操作任意次。

删除子字符串 "ab" 并得到 x 分。
比方说，从 "cabxbae" 删除 ab ，得到 "cxbae" 。
删除子字符串"ba" 并得到 y 分。
比方说，从 "cabxbae" 删除 ba ，得到 "cabxe" 。
请返回对 s 字符串执行上面操作若干次能得到的最大得分。

 

示例 1：

输入：s = "cdbcbbaaabab", x = 4, y = 5
输出：19
解释：
- 删除 "cdbcbbaaabab" 中加粗的 "ba" ，得到 s = "cdbcbbaaab" ，加 5 分。
- 删除 "cdbcbbaaab" 中加粗的 "ab" ，得到 s = "cdbcbbaa" ，加 4 分。
- 删除 "cdbcbbaa" 中加粗的 "ba" ，得到 s = "cdbcba" ，加 5 分。
- 删除 "cdbcba" 中加粗的 "ba" ，得到 s = "cdbc" ，加 5 分。
总得分为 5 + 4 + 5 + 5 = 19 。
示例 2：

输入：s = "aabbaaxybbaabb", x = 5, y = 4
输出：20
 

提示：

1 <= s.length <= 105
1 <= x, y <= 104
s 只包含小写英文字母。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-score-from-removing-substrings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

贪心算法

假设消除ab的收益最大，如果不是，则转换成消除ab的收益最大

• 如果遇到一个a，字符a的计数增加

• 如果遇到一个b，并且字符a的数量大于零，那么字符a的数量减去1，结果加上消除a的收益x

• 如果遇到一个b，并且字符a的数量等于零，那么字符b的数量加上1

• ab消除完成后，消除ba，查看字符a与字符b的数量的最小值，即能消除的最大的数目再乘以y

class Solution {
    public int maximumGain(String s, int x, int y) {
        int n = s.length();
        if (x < y) {                                                              //如果x<y交换x和y，交换所有的a和b
            x = x ^ y;
            y = x ^ y;
            x = x ^ y;
            s = s.replaceAll("a", "-1");
            s = s.replaceAll("b", "a");
            s = s.replaceAll("-1", "b");
        }

        int ret = 0;
        int i = 0;
        while (i < n) {
            while (i < n && s.charAt(i) != 'a' && s.charAt(i) != 'b') i++;      //过渡到下一个连续区间
            int ca = 0, cb = 0;
            while (i < n && (s.charAt(i) == 'a' || s.charAt(i) == 'b')) {       //如果是连续的a和b，那么在该区间中，a前b后一定能消除ab，剩下的就是ba
                if (s.charAt(i) == 'a') {
                    ca++;
                } else {
                    if (ca > 0) {                                               //a在前b在后，可以消除ab
                        ca--;
                        ret += x;
                    } else {
                        cb++;
                    }
                }
                i++;
            }
            ret += Math.min(ca, cb) * y;                                        //剩下的ba的数量
        }
        return ret;
    }
}

赏

谢谢你请我吃糖果

微信