删除子字符串的最大得分
#算法
给你一个字符串 s 和两个整数 x 和 y 。你可以执行下面两种操作任意次。
- 删除子字符串 "ab" 并得到 x 分。比方说，从 "cabxbae" 删除 ab ，得到 "cxbae"
- 删除子字符串"ba" 并得到 y 分。比方说，从 "cabxbae" 删除 ba ，得到 "cabxe"
- 请返回对 s 字符串执行上面操作若干次能得到的最大得分。
对称思想： 如果ab对应的x不是大的，交换a、b此时a代表'b'，b代表'a'，大大简化了代码。
贪心思想： 尽可能构造得分大的组合，最后区块结束时（以遇到其他字符为标志）再构造得分小的。
class Solution {
public:
int maximumGain(string s, int x, int y) {
s+='#';
char a = 'a', b = 'b';
if (x < y) {
swap(x, y);//确保ab是大的，这里ab不一定指的是'a'和'b'，也可能是反过来
swap(a, b);
}
int ans = 0, cnt1 = 0, cnt2 = 0;//a的数量和b的数量
for (char c : s) {
if (c == a)cnt1++;
else if (c == b) {
if (cnt1){//和a配对，不加cnt2，减cnt1
ans += x;cnt1--;
}
else cnt2++;
}
else {//如果是其他字符，统计剩下可以构造的ba
ans += min(cnt1, cnt2) * y;
cnt1 = cnt2 = 0;//开启下一轮，每轮彼此独立
}
}
return ans;
}
};