题目描述
给定一个字符串 s
和两个整数 x
和 y
。你可以执行下面两种操作任意次。
- 删除子字符串
"ab"
并得到x
分。比方说,从"cabxbae"
删除"ab"
,得到"cxbae"
。 - 删除子字符串
"ba"
并得到y
分。比方说,从"cabxbae"
删除"ba"
,得到"cabxe"
。
请返回对 s
字符串执行上面操作若干次能得到的最大得分。
样例
输入:s = "cdbcbbaaabab", x = 4, y = 5
输出:19
解释:
- 删除 "cdbcbbaaa[ba]b" 中的 "ba",得到 s = "cdbcbbaaab",加 5 分。
- 删除 "cdbcbbaa[ab]" 中的 "ab",得到 s = "cdbcbbaa",加 4 分。
- 删除 "cdbcb[ba]a" 中的 "ba",得到 s = "cdbcba",加 5 分。
- 删除 "cdbc[ba]" 中的 "ba",得到 s = "cdbc",加 5 分。
总得分为 5 + 4 + 5 + 5 = 19。
输入:s = "aabbaaxybbaabb", x = 5, y = 4
输出:20
限制
1 <= s.length <= 10^5
1 <= x, y <= 10^4
s
只包含小写英文字母。
算法1
(贪心,栈) $O(n)$
- 如果
x >= y
,则可以先消除"ab"
然后消除"ba"
。否则,先消除"ba"
然后消除"ab"
。 - 贪心的正确性:每次删除都会同时减少一个
a
和一个b
,最终的删掉ab
或ba
的总数是固定的。不妨假设x >= y
(否则可以交换a
和b
以及x
和y
),则先删除了ba
可能导致之后的某个ab
无法删除,从而丢掉高分。 - 消除操作可以依靠栈进行。
时间复杂度
- 遍历两次字符串,故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储栈和临时字符串。
C++ 代码
class Solution {
public:
int maximumGain(string s, int x, int y) {
stack<char> st;
int ans = 0;
for (char c : s) {
if (x >= y && !st.empty() && st.top() == 'a' && c == 'b') {
ans += x;
st.pop();
} else if (x < y && !st.empty() && st.top() == 'b' && c == 'a') {
ans += y;
st.pop();
} else {
st.push(c);
}
}
string t;
while (!st.empty()) {
t.push_back(st.top());
st.pop();
}
for (char c : t) {
if (!st.empty() && st.top() == 'a' && c == 'b') {
ans += y;
st.pop();
} else if (!st.empty() && st.top() == 'b' && c == 'a') {
ans += x;
st.pop();
} else {
st.push(c);
}
}
return ans;
}
};
算法2
(贪心) $O(n)$
- 贪心思路同 1。
- 遍历过程中,不妨假设
x >= y
,聚焦在每一组连续的a
和b
的子串上。 - 对于一组子串,从左到右遍历过程中,用两个变量分别记录
a
和b
的个数,具体如下:- 如果当前为
a
,则a
的个数加 1。 - 如果当前为
b
,则考虑是否有剩余的a
与其匹配,即a
的个数是否大于 0,这是因为a
的个数大于 0 一定说明当前位置除去ab
以后,是以a
结尾的。- 如果有,则
a
的个数减 1,答案加上x
。 - 如果没有,则
b
的个数加 1。
- 如果有,则
- 子串遍历结束后,剩下的都是可以组成
ba
的情况,答案累加a
或b
中较少的个数乘y
。
- 如果当前为
时间复杂度
- 遍历字符串最多两次,故总时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int maximumGain(string s, int x, int y) {
const int n = s.size();
if (x < y) {
for (int i = 0; i < n; i++) {
if (s[i] == 'a') s[i] = 'b';
else if (s[i] == 'b') s[i] = 'a';
}
swap(x, y);
}
int ans = 0, ta = 0, tb = 0;
for (int i = 0; i < n; i++) {
if (s[i] == 'a') {
ta++;
} else if (s[i] == 'b') {
if (ta > 0) {
ta--;
ans += x;
} else {
tb++;
}
} else {
ans += min(ta, tb) * y;
ta = tb = 0;
}
}
return ans + min(ta, tb) * y;
}
};