方法一:暴力,会超时
思路是,优先匹配分高的进行替换,不能替换了,再去替换一次分低的进行替换,再回头检查是否凑成了分高的
class Solution {
public int maximumGain(String s, int x, int y) {
int i = x, j = y;
String a = "ab", b = "ba";
if (y > x) {
b = "ab";
a = "ba";
i = y;
j = x;
}
int ans = 0;
while (true) {
String n = s.replace(a, "");
if (n.equals(s)) {
String t = s.replace(b, "");
if (t.equals(s)) {
break;
} else {
ans += ((s.length() - t.length()) / 2 * j);
s = t;
}
} else {
ans += ((s.length() - n.length()) / 2 * i);
s = n;
}
}
return ans;
}
}
方法二:分段 贪心处理
思路是处理字符串 S,找出每一段连续的,只由 a 和 b 构成的连续子串
为了防止需要特殊处理最后一段,所以往结尾最加一个哨兵 c
然后对子串从后往前进行处理,优先匹配出得分高的(假设是字符串 a),然后在得到匹配完所有的 a 字符串的之后,通过 ac 和 bc 的字符记录器,可以快速算出剩余的字符串中能够匹配出 b 的次数
class Solution {
public int maximumGain(String s, int x, int y) {
String a = "ab", b = "ba";
int p = x, q = y;
if (x < y) {
a = "ba";
b = "ab";
p = y;
q = x;
}
s = s + "c"; // 结尾加个哨兵
int n = s.length();
char[] cs = s.toCharArray();
int ans = 0;
int ac = 0, bc = 0; // 记录当前连续子串中 a 的数量和 b 数量
for (int i = 0, start = -1; i < n; i++) { // start 是记录当前连续子串的起始位置
if (cs[i] != 'a' && cs[i] != 'b') {
if (start != -1) {
String sub = s.substring(start, i); // 得到一段连续的,只由 a 和 b 组成的子串
int t = sub.length();
int aCnt = 0; // 匹配字符串 a 的次数
for (int j = t - 1, u = 0; j >= 0; j--) {
if (sub.charAt(j) == a.charAt(1)) {
u++;
} else {
if (u > 0) {
u--;
aCnt++;
}
}
}
ac -= aCnt;
bc -= aCnt;
int bCnt = Math.min(ac, bc); // // 在匹配完所有的字符串 a 的情况下,剩下的字符中,可以匹配出 b 的次数
ans += aCnt * p + bCnt * q;
start = -1;
ac = 0;
bc = 0;
}
} else {
if (cs[i] == 'a') ac++;
if (cs[i] == 'b') bc++;
if (start == -1) start = i;
}
}
return ans;
}
}