You are given a string s and two integers x and y. You can perform two types of operations any number of times.
Remove substring "ab" and gain x points.
For example, when removing "ab" from "cabxbae" it becomes "cxbae".
Remove substring "ba" and gain y points.
For example, when removing "ba" from "cabxbae" it becomes "cabxe".
Return the maximum points you can gain after applying the above operations on s.
Example 1:
Input: s = "cdbcbbaaabab", x = 4, y = 5
Output: 19
Explanation:
- Remove the "ba" underlined in "cdbcbbaaabab". Now, s = "cdbcbbaaab" and 5 points are added to the score.
- Remove the "ab" underlined in "cdbcbbaaab". Now, s = "cdbcbbaa" and 4 points are added to the score.
- Remove the "ba" underlined in "cdbcbbaa". Now, s = "cdbcba" and 5 points are added to the score.
- Remove the "ba" underlined in "cdbcba". Now, s = "cdbc" and 5 points are added to the score.
Total score = 5 + 4 + 5 + 5 = 19.
Example 2:
Input: s = "aabbaaxybbaabb", x = 5, y = 4
Output: 20
Constraints:
1 <= s.length <= 105
1 <= x, y <= 104
s consists of lowercase English letters.
Solution:
We greedily remove the pattern with greater points, then remove the other pattern.
class Solution {
public int maximumGain(String s, int x, int y) {
Deque<Character> removeMax = new ArrayDeque();
Deque<Character> removeMin = new ArrayDeque();
char first = x >= y ? 'a' : 'b';
char second = x >= y ? 'b' : 'a';
int max = Math.max(x, y);
int min = Math.min(x, y);
int res = 0;
for (int i = 0; i < s.length(); i ++) {
char c = s.charAt(i);
if (!removeMax.isEmpty() && removeMax.peekLast() == first && c == second) {
removeMax.pollLast();
res += max;
} else {
removeMax.offerLast(c);
}
}
while (!removeMax.isEmpty()) {
char c = removeMax.pollLast();
if (!removeMin.isEmpty() && c == second && removeMin.peekLast() == first) {
removeMin.pollLast();
res += min;
} else {
removeMin.offerLast(c);
}
}
return res;
}
}
public int maximumGain(String s, int x, int y) {
StringBuilder sb = new StringBuilder(s);
if (x > y) {
return remove(sb, "ab", x) + remove(sb, "ba", y);
}
return remove(sb, "ba", y) + remove(sb, "ab", x);
}
private int remove(StringBuilder sb, String pattern, int point) {
int i = 0, res = 0;
for (int j = 0; j < sb.length(); j++) {
sb.setCharAt(i++, sb.charAt(j));
if (i > 1 && sb.charAt(i-2) == pattern.charAt(0) && sb.charAt(i-1) == pattern.charAt(1)) {
i -= 2;
res += point;
}
}
sb.setLength(i);
return res;
}