登录[Python3/Java/C++/Go/TypeScript] 一题一解：贪心（清晰题解）
方法一：贪心
我们不妨假设子字符串 "ab" 的得分总是不低于子字符串 "ba" 的得分，如果不是，我们可以交换 "a" 和 "b"，同时交换 $x$ 和 $y$。
接下来，我们只需要考虑字符串中只包含 "a" 和 "b" 的情况。如果字符串中包含其他字符，我们可以将其视为一个分割点，将字符串分割成若干个只包含 "a" 和 "b" 的子字符串，然后分别计算每个子字符串的得分。
我们观察发现，对于一个只包含 "a" 和 "b" 的子字符串，无论采取什么样的操作，最后一定只剩下一种字符，或者空串。由于每次操作都会同时删除一个 "a" 和一个 "b"，因此总的操作次数一定是固定的。我们可以贪心地先删除 "ab"，再删除 "ba"，这样可以保证得分最大。
因此，我们可以使用两个变量 $\textit{cnt1}$ 和 $\textit{cnt2}$ 分别记录 "a" 和 "b" 的数量，然后遍历字符串，根据当前字符的不同情况更新 $\textit{cnt1}$ 和 $\textit{cnt2}$，并计算得分。
对于当前遍历到的字符 $c$：
- 如果 $c$ 是 "a"，由于要先删除 "ab"，因此此时我们不消除该字符，只增加 $\textit{cnt1}$；
- 如果 $c$ 是 "b"，如果此时 $\textit{cnt1} > 0$，我们可以消除一个 "ab"，并增加 $x$ 分，否则我们只能增加 $\textit{cnt2}$；
- 如果 $c$ 是其他字符，那么对于该子字符串，我们剩下了一个 $\textit{cnt2}$ 个 "b" 和 $\textit{cnt1}$ 个 "a"，我们可以消除 $\min(\textit{cnt1}, \textit{cnt2})$ 个 "ab"，并增加 $y$ 分。
遍历结束后，我们还需要额外处理一下剩余的 "ab"，增加若干个 $y$ 分。
###python
class Solution:
def maximumGain(self, s: str, x: int, y: int) -> int:
a, b = "a", "b"
if x < y:
x, y = y, x
a, b = b, a
ans = cnt1 = cnt2 = 0
for c in s:
if c == a:
cnt1 += 1
elif c == b:
if cnt1:
ans += x
cnt1 -= 1
else:
cnt2 += 1
else:
ans += min(cnt1, cnt2) * y
cnt1 = cnt2 = 0
ans += min(cnt1, cnt2) * y
return ans
###java
class Solution {
public int maximumGain(String s, int x, int y) {
char a = 'a', b = 'b';
if (x < y) {
int t = x;
x = y;
y = t;
char c = a;
a = b;
b = c;
}
int ans = 0, cnt1 = 0, cnt2 = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {
char c = s.charAt(i);
if (c == a) {
cnt1++;
} else if (c == b) {
if (cnt1 > 0) {
ans += x;
cnt1--;
} else {
cnt2++;
}
} else {
ans += Math.min(cnt1, cnt2) * y;
cnt1 = 0;
cnt2 = 0;
}
}
ans += Math.min(cnt1, cnt2) * y;
return ans;
}
}
###cpp
class Solution {
public:
int maximumGain(string s, int x, int y) {
char a = 'a', b = 'b';
if (x < y) {
swap(x, y);
swap(a, b);
}
int ans = 0, cnt1 = 0, cnt2 = 0;
for (char c : s) {
if (c == a) {
cnt1++;
} else if (c == b) {
if (cnt1) {
ans += x;
cnt1--;
} else {
cnt2++;
}
} else {
ans += min(cnt1, cnt2) * y;
cnt1 = 0;
cnt2 = 0;
}
}
ans += min(cnt1, cnt2) * y;
return ans;
}
};
###go
func maximumGain(s string, x int, y int) (ans int) {
a, b := 'a', 'b'
if x < y {
x, y = y, x
a, b = b, a
}
var cnt1, cnt2 int
for _, c := range s {
if c == a {
cnt1++
} else if c == b {
if cnt1 > 0 {
ans += x
cnt1--
} else {
cnt2++
}
} else {
ans += min(cnt1, cnt2) * y
cnt1, cnt2 = 0, 0
}
}
ans += min(cnt1, cnt2) * y
return
}
###ts
function maximumGain(s: string, x: number, y: number): number {
let [a, b] = ['a', 'b'];
if (x < y) {
[x, y] = [y, x];
[a, b] = [b, a];
}
let [ans, cnt1, cnt2] = [0, 0, 0];
for (let c of s) {
if (c === a) {
cnt1++;
} else if (c === b) {
if (cnt1) {
ans += x;
cnt1--;
} else {
cnt2++;
}
} else {
ans += Math.min(cnt1, cnt2) * y;
cnt1 = 0;
cnt2 = 0;
}
}
ans += Math.min(cnt1, cnt2) * y;
return ans;
}
###rust
impl Solution {
pub fn maximum_gain(s: String, mut x: i32, mut y: i32) -> i32 {
let (mut a, mut b) = ('a', 'b');
if x < y {
std::mem::swap(&mut x, &mut y);
std::mem::swap(&mut a, &mut b);
}
let mut ans = 0;
let mut cnt1 = 0;
let mut cnt2 = 0;
for c in s.chars() {
if c == a {
cnt1 += 1;
} else if c == b {
if cnt1 > 0 {
ans += x;
cnt1 -= 1;
} else {
cnt2 += 1;
}
} else {
ans += cnt1.min(cnt2) * y;
cnt1 = 0;
cnt2 = 0;
}
}
ans += cnt1.min(cnt2) * y;
ans
}
}
###js
function maximumGain(s, x, y) {
let [a, b] = ['a', 'b'];
if (x < y) {
[x, y] = [y, x];
[a, b] = [b, a];
}
let [ans, cnt1, cnt2] = [0, 0, 0];
for (let c of s) {
if (c === a) {
cnt1++;
} else if (c === b) {
if (cnt1) {
ans += x;
cnt1--;
} else {
cnt2++;
}
} else {
ans += Math.min(cnt1, cnt2) * y;
cnt1 = 0;
cnt2 = 0;
}
}
ans += Math.min(cnt1, cnt2) * y;
return ans;
}
###cs
public class Solution {
public int MaximumGain(string s, int x, int y) {
char a = 'a', b = 'b';
if (x < y) {
(x, y) = (y, x);
(a, b) = (b, a);
}
int ans = 0, cnt1 = 0, cnt2 = 0;
foreach (char c in s) {
if (c == a) {
cnt1++;
} else if (c == b) {
if (cnt1 > 0) {
ans += x;
cnt1--;
} else {
cnt2++;
}
} else {
ans += Math.Min(cnt1, cnt2) * y;
cnt1 = 0;
cnt2 = 0;
}
}
ans += Math.Min(cnt1, cnt2) * y;
return ans;
}
}
时间复杂度 $O(n)$，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(1)$。
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~
