class Solution {
public:
int maximumGain(string s, int x, int y) {
}
};
1717. 删除子字符串的最大得分
给你一个字符串 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 <= 1051 <= x, y <= 104s 只包含小写英文字母。原站题解
java 解法, 执行用时: 28 ms, 内存消耗: 42.9 MB, 提交时间: 2023-09-23 00:49:34
class Solution {
public int maximumGain(String s, int x, int y) {
int points = 0;
char c1 = 'a', c2 = 'b';
if (x < y) {
c1 = 'b';
c2 = 'a';
int temp = x;
x = y;
y = temp;
}
int count1 = 0, count2 = 0;
int length = s.length();
for (int i = 0; i < length; i++) {
char curr = s.charAt(i);
if (curr == c1) {
count1++;
} else if (curr == c2) {
if (count1 > 0) {
count1--;
points += x;
} else {
count2++;
}
}
char next = i < length - 1 ? s.charAt(i + 1) : ' ';
if (next != c1 && next != c2) {
points += y * Math.min(count1, count2);
count1 = 0;
count2 = 0;
}
}
return points;
}
}
java 解法, 执行用时: 115 ms, 内存消耗: 43 MB, 提交时间: 2023-09-23 00:49:21
class Solution {
int points = 0;
public int maximumGain(String s, int x, int y) {
if (x >= y) {
s = remove1(s, x);
s = remove2(s, y);
} else {
s = remove2(s, y);
s = remove1(s, x);
}
return points;
}
public String remove1(String s, int x) {
StringBuffer sb = new StringBuffer();
int length = s.length();
int index = 0;
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (index > 0 && c == 'b' && sb.charAt(index - 1) == 'a') {
points += x;
sb.deleteCharAt(index - 1);
index--;
} else {
sb.append(c);
index++;
}
}
return sb.toString();
}
public String remove2(String s, int y) {
StringBuffer sb = new StringBuffer();
int length = s.length();
int index = 0;
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (index > 0 && c == 'a' && sb.charAt(index - 1) == 'b') {
points += y;
sb.deleteCharAt(index - 1);
index--;
} else {
sb.append(c);
index++;
}
}
return sb.toString();
}
}
cpp 解法, 执行用时: 56 ms, 内存消耗: 16.9 MB, 提交时间: 2023-09-23 00:48:42
class Solution
{
public:
int maximumGain(string s, int x, int y)
{
int cnt_a = 0, cnt_b = 0;
int res = 0;
for (char c: s)
{
if (c == 'a')
{
if (x < y && cnt_b > 0) // ba 的情况
{
res += y;
cnt_b --;
}
else
cnt_a ++;
}
else if (c == 'b')
{
if (x >= y && cnt_a > 0) // ab 的情况
{
res += x;
cnt_a --;
}
else
cnt_b ++;
}
else
{
if (cnt_a != 0 && cnt_b != 0)
res += min(x, y) * min(cnt_a, cnt_b);
cnt_a = 0;
cnt_b = 0;
}
}
if (cnt_a && cnt_b)
res += std::min(x, y) * std::min(cnt_a, cnt_b);
return res;
}
};
python3 解法, 执行用时: 204 ms, 内存消耗: 16.6 MB, 提交时间: 2023-09-23 00:48:21
class Solution:
def maximumGain(self, s: str, x: int, y: int) -> int:
cnt_a = 0
cnt_b = 0
res = 0
for c in s:
if c == 'b':
if x >= y and cnt_a > 0: # ab 的情况
res += x
cnt_a -= 1
else:
cnt_b += 1
elif c == 'a':
if y > x and cnt_b > 0: # ba 的情况
res += y
cnt_b -= 1
else:
cnt_a += 1
else: #这一个窗口截止了
if cnt_a > 0 and cnt_b > 0:
res += min(x, y) * min(cnt_a, cnt_b)
cnt_a = 0
cnt_b = 0
if cnt_a and cnt_b:
res += min(x, y) * min(cnt_a, cnt_b)
return res
golang 解法, 执行用时: 24 ms, 内存消耗: 6.4 MB, 提交时间: 2023-09-23 00:47:57
func maximumGain(s string, x int, y int) int {
// 因为只能删掉a b两个字符, 所以其他字符可以看成分隔符
// 对于一个只有ab组成的字符串来说,无论是什么排列顺序,最后总能消除min(cntA, cntB)个对数
// 所以目标转换成优先消除ab ba中分数较高的pattern
// 用栈来寄存当前的字符串,遇到高分pattern就先删除高分pattern,最后字符串结束时处理低分pattern
stack := []rune{}
priorityPattern := 'a'
if x < y {
priorityPattern = 'b'
x, y = y, x
}
res := 0
for _, b := range s+"c" {
if b == 'a' || b == 'b' {
// 优先找mn组合(mn是相对分数较高的那个模式)
if len(stack) > 0 && stack[len(stack)-1] == priorityPattern && b != priorityPattern {
// 找到mn组合
res += x
// pop
stack = stack[:len(stack)-1]
} else {
// push
stack = append(stack, b)
}
} else {
// 其他字符,处理掉当前栈
// 栈上只可能形成 nnnnnmmmmm的形式
// 两头走加速，实际受cacheline影响，不见得能快多少:(
l, r := 0 ,len(stack)-1
for l < r {
if stack[l] == stack[r] {
break
}
res += y
l++
r--
}
stack = stack[:0]
}
}
return res
}