Formatted question description: https://leetcode.ca/all/1717.html
1717. Maximum Score From Removing Substrings
Level
Medium
Description
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 gainx
points.- For example, when removing
"ab"
from"cabxbae"
it becomes"cxbae"
.
- For example, when removing
- Remove substring
"ba"
and gainy
points.- For example, when removing
"ba"
from"cabxbae"
it becomes"cabxe"
.
- For example, when removing
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 <= 10^5
1 <= x, y <= 10^4
s
consists of lowercase English letters.
Solution
Use a greedy approach. If x >= y
, then consider removing "ab"
first and removing "ba"
next. Otherwise, consider removing "ba"
first and removing "ab"
next.
When removing substrings, update the score and generate the new string after removing the substrings, so that the next steps can be proceeded as well.
Finally, return the score.
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();
}
}