class Solution:
def maximumGain(self, s: str, x: int, y: int) -> int:
def remove_pattern(s, first, second, score):
stack = []
total = 0
for c in s:
if stack and stack[-1] == first and c == second:
stack.pop()
total += score
else:
stack.append(c)
return ''.join(stack), total
res = 0
# Remove the higher value pattern first
if x >= y:
s, gain = remove_pattern(s, 'a', 'b', x)
res += gain
s, gain = remove_pattern(s, 'b', 'a', y)
res += gain
else:
s, gain = remove_pattern(s, 'b', 'a', y)
res += gain
s, gain = remove_pattern(s, 'a', 'b', x)
res += gain
return res
class Solution {
public:
int maximumGain(string s, int x, int y) {
auto removePattern = [](string &s, char first, char second, int score) {
stack<char> stk;
int total = 0;
string res = "";
for (char c : s) {
if (!stk.empty() && stk.top() == first && c == second) {
stk.pop();
total += score;
} else {
stk.push(c);
}
}
// Build the remaining string
string remain = "";
while (!stk.empty()) {
remain += stk.top();
stk.pop();
}
reverse(remain.begin(), remain.end());
s = remain;
return total;
};
int total = 0;
if (x >= y) {
total += removePattern(s, 'a', 'b', x);
total += removePattern(s, 'b', 'a', y);
} else {
total += removePattern(s, 'b', 'a', y);
total += removePattern(s, 'a', 'b', x);
}
return total;
}
};
class Solution {
public int maximumGain(String s, int x, int y) {
StringBuilder sb = new StringBuilder();
int res = 0;
if (x >= y) {
String[] result = removePattern(s, 'a', 'b', x);
res += Integer.parseInt(result[1]);
result = removePattern(result[0], 'b', 'a', y);
res += Integer.parseInt(result[1]);
} else {
String[] result = removePattern(s, 'b', 'a', y);
res += Integer.parseInt(result[1]);
result = removePattern(result[0], 'a', 'b', x);
res += Integer.parseInt(result[1]);
}
return res;
}
private String[] removePattern(String s, char first, char second, int score) {
StringBuilder stack = new StringBuilder();
int total = 0;
for (char c : s.toCharArray()) {
if (stack.length() > 0 && stack.charAt(stack.length() - 1) == first && c == second) {
stack.deleteCharAt(stack.length() - 1);
total += score;
} else {
stack.append(c);
}
}
return new String[]{stack.toString(), String.valueOf(total)};
}
}
var maximumGain = function(s, x, y) {
function removePattern(str, first, second, score) {
let stack = [];
let total = 0;
for (let c of str) {
if (stack.length > 0 && stack[stack.length - 1] === first && c === second) {
stack.pop();
total += score;
} else {
stack.push(c);
}
}
return [stack.join(''), total];
}
let res = 0;
if (x >= y) {
let out = removePattern(s, 'a', 'b', x);
s = out[0];
res += out[1];
out = removePattern(s, 'b', 'a', y);
s = out[0];
res += out[1];
} else {
let out = removePattern(s, 'b', 'a', y);
s = out[0];
res += out[1];
out = removePattern(s, 'a', 'b', x);
s = out[0];
res += out[1];
}
return res;
};
Given a string s and two integers x and y, you are allowed to repeatedly remove either the substring "ab" from s for x points or the substring "ba" for y points. Each removal shortens the string, and you may continue removing as long as one of these substrings exists. Your task is to maximize the total score by strategically removing substrings in the best order.
1 <= s.length <= 10^5, 1 <= x, y <= 10^4.
At first glance, it might seem that removing substrings as you find them would be sufficient. However, because removing one pattern may create opportunities to remove the other, the order in which you remove the substrings "ab" and "ba" becomes important. If you remove the higher-value pattern first, you may maximize your score, as lower-value removals could block higher-value ones if done prematurely.
A brute-force approach would try all possible orders, but with string lengths up to 100,000, that's computationally infeasible. Instead, we need an efficient way to simulate removals and ensure we always prioritize the most valuable options.
"ab" or "ba".This approach ensures that the most valuable removals are done first, and the stack-based simulation allows for linear-time processing, which is essential for large input sizes.
Input: s = "cdbababc", x = 4, y = 5
y > x, we remove "ba" (worth 5 points) first.
"ba": remove it, score = 5. New string: "cdababc" -> "cdabc""ba" again: remove it, score = 5 + 5 = 10. New string: "cdabc" -> "cdc""ab" (worth 4 points):
"ab" found in "cdc". So score remains 10.
The order of removal affects the outcome; had we removed "ab" first, we would have scored less.
To maximize the score from removing substrings in this problem, it's crucial to always remove the higher-value pattern first. By simulating removals with a stack, we ensure linear-time processing and avoid missing valuable removal opportunities. This strategy leverages the greedy principle and efficient data structures, making the solution both elegant and practical for large inputs.