Maximum Score From Removing Substrings
Maximum Score From Removing Substrings is a medium stack problem solved with the stack basics pattern.
The best approach, optimal (greedy with two stack passes), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every removal) up.
Problem
You are given a string s and two integers x and y. You may repeat either of these moves as often as you like:
- Delete a substring
"ab"fromsand earnxpoints. - Delete a substring
"ba"fromsand earnypoints.
After a deletion, the remaining characters close the gap, so new pairs can form. Return the maximum total number of points you can earn.
Examples
Example 1
- Input
s = "xbaabay", x = 4, y = 6- Output
12- Why
- Remove "ba" to get "xabay" (+6), then remove "ba" again to get "xay" (+6).
Example 2
- Input
s = "abab", x = 2, y = 3- Output
5- Why
- Remove the middle "ba" (+3), which leaves "ab" (+2). Removing "ab" first would only allow 2 + 2 = 4.
Example 3
- Input
s = "kbbaxaab", x = 5, y = 1- Output
6- Why
- The 'x' splits the string. "kbba" gives one "ba" (+1) and "aab" gives one "ab" (+5).
Constraints
1 <= s.length <= 10^51 <= x, y <= 10^4sconsists of lowercase English letters.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every removal) | O(2ⁿ · n) | O(2ⁿ · n) |
| Optimal (greedy with two stack passes) | O(n) | O(n) |
1Brute force (try every removal)
O(2ⁿ · n)The number of distinct intermediate strings can grow exponentially, and each one is scanned and copied in O(n).O(2ⁿ · n)The memo stores every distinct intermediate string.Explore every possible order of removals. From a string, try deleting each occurrence of "ab" or "ba", recurse on the shorter string, and keep the best total. Memoize on the string so repeated states are solved once.
- best(t) = 0 if t contains neither pair.
- Otherwise, for each index i where t[i..i+1] is "ab" (or "ba"), consider x (or y) + best(t without those two letters).
- Return the maximum, caching the answer for t.
class Solution {
private Map<String, Integer> memo = new HashMap<>();
private int x, y;
public int maximumGain(String s, int x, int y) {
this.x = x;
this.y = y;
return best(s);
}
private int best(String t) {
Integer cached = memo.get(t);
if (cached != null) return cached;
int res = 0;
for (int i = 0; i + 1 < t.length(); i++) {
char c = t.charAt(i), d = t.charAt(i + 1);
String rest = null;
int gain = 0;
if (c == 'a' && d == 'b') gain = x;
else if (c == 'b' && d == 'a') gain = y;
if (gain > 0) {
rest = t.substring(0, i) + t.substring(i + 2);
res = Math.max(res, gain + best(rest));
}
}
memo.put(t, res);
return res;
}
}class Solution:
def maximumGain(self, s: str, x: int, y: int) -> int:
memo = {}
def best(t: str) -> int:
if t in memo:
return memo[t]
res = 0
for i in range(len(t) - 1):
pair = t[i:i + 2]
gain = x if pair == "ab" else y if pair == "ba" else 0
if gain:
res = max(res, gain + best(t[:i] + t[i + 2:]))
memo[t] = res
return res
return best(s)class Solution {
public:
int maximumGain(string s, int x, int y) {
this->x = x;
this->y = y;
return best(s);
}
private:
unordered_map<string, int> memo;
int x, y;
int best(const string& t) {
auto it = memo.find(t);
if (it != memo.end()) return it->second;
int res = 0;
for (int i = 0; i + 1 < (int)t.size(); i++) {
int gain = 0;
if (t[i] == 'a' && t[i + 1] == 'b') gain = x;
else if (t[i] == 'b' && t[i + 1] == 'a') gain = y;
if (gain > 0) {
string rest = t.substr(0, i) + t.substr(i + 2);
res = max(res, gain + best(rest));
}
}
memo[t] = res;
return res;
}
};function maximumGain(s, x, y) {
const memo = new Map();
const best = (t) => {
if (memo.has(t)) return memo.get(t);
let res = 0;
for (let i = 0; i + 1 < t.length; i++) {
let gain = 0;
if (t[i] === 'a' && t[i + 1] === 'b') gain = x;
else if (t[i] === 'b' && t[i + 1] === 'a') gain = y;
if (gain > 0) {
res = Math.max(res, gain + best(t.slice(0, i) + t.slice(i + 2)));
}
}
memo.set(t, res);
return res;
};
return best(s);
}2Optimal (greedy with two stack passes)
O(n)Each pass pushes and pops each character at most once.O(n)The two stacks hold up to n characters.Inside a block of only 'a' and 'b', the number of pairs you can remove in total is fixed (the smaller letter count), so you want as many of the valuable pair as possible. Removing the valuable pair first never blocks another valuable one. Run a stack pass that deletes every valuable pair (top is its first letter and the current char is its second), then run a second stack pass on the leftover string that deletes the cheaper pair.
- Let first/second be the letters of the more valuable pair ("ab" if x >= y, else "ba"), with values hi and lo.
- Pass 1: push characters onto a stack; when the current char is
secondand the top isfirst, pop and add hi. - Pass 2: scan the leftover stack contents the same way, removing the reversed pair (
secondthenfirst) and adding lo. - Return the total.
class Solution {
public int maximumGain(String s, int x, int y) {
char first = 'a', second = 'b';
int hi = x, lo = y;
if (x < y) {
first = 'b';
second = 'a';
hi = y;
lo = x;
}
int score = 0;
StringBuilder st = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == second && st.length() > 0 && st.charAt(st.length() - 1) == first) {
st.deleteCharAt(st.length() - 1);
score += hi;
} else {
st.append(c);
}
}
StringBuilder st2 = new StringBuilder();
for (int i = 0; i < st.length(); i++) {
char c = st.charAt(i);
if (c == first && st2.length() > 0 && st2.charAt(st2.length() - 1) == second) {
st2.deleteCharAt(st2.length() - 1);
score += lo;
} else {
st2.append(c);
}
}
return score;
}
}class Solution:
def maximumGain(self, s: str, x: int, y: int) -> int:
first, second, hi, lo = "a", "b", x, y
if x < y:
first, second, hi, lo = "b", "a", y, x
score = 0
st = []
for c in s:
if c == second and st and st[-1] == first:
st.pop()
score += hi
else:
st.append(c)
st2 = []
for c in st:
if c == first and st2 and st2[-1] == second:
st2.pop()
score += lo
else:
st2.append(c)
return scoreclass Solution {
public:
int maximumGain(string s, int x, int y) {
char first = 'a', second = 'b';
int hi = x, lo = y;
if (x < y) {
first = 'b';
second = 'a';
hi = y;
lo = x;
}
int score = 0;
string st;
for (char c : s) {
if (c == second && !st.empty() && st.back() == first) {
st.pop_back();
score += hi;
} else {
st.push_back(c);
}
}
string st2;
for (char c : st) {
if (c == first && !st2.empty() && st2.back() == second) {
st2.pop_back();
score += lo;
} else {
st2.push_back(c);
}
}
return score;
}
};function maximumGain(s, x, y) {
let first = 'a', second = 'b', hi = x, lo = y;
if (x < y) {
first = 'b';
second = 'a';
hi = y;
lo = x;
}
let score = 0;
const st = [];
for (const c of s) {
if (c === second && st.length > 0 && st[st.length - 1] === first) {
st.pop();
score += hi;
} else {
st.push(c);
}
}
const st2 = [];
for (const c of st) {
if (c === first && st2.length > 0 && st2[st2.length - 1] === second) {
st2.pop();
score += lo;
} else {
st2.push(c);
}
}
return score;
}Edge cases to test
- x == y: every removable pair is worth the same
- Removing one pair glues its neighbours together and can create a new pair
- Letters other than 'a' and 'b' act as walls that no pair can cross
- No 'a' or no 'b' at all: the answer is 0
Hints
Hint 1
Removing a pair can only create new pairs from its neighbours. Does it ever hurt to grab the more valuable pair first?
Hint 2
Greedily remove every copy of the more valuable pair, then every copy of the other pair in what remains.
Hint 3
A stack removes all copies of a two-letter pattern in one pass, including the ones that appear after earlier removals.
FAQ
What is the best time complexity for Maximum Score From Removing Substrings?
Optimal (greedy with two stack passes) runs in O(n) time and O(n) extra space. Each pass pushes and pops each character at most once.
Which pattern does Maximum Score From Removing Substrings use?
It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.
Is there a brute force solution for Maximum Score From Removing Substrings?
Yes. Brute force (try every removal) takes O(2ⁿ · n) time and O(2ⁿ · n) space. Explore every possible order of removals.
Which edge cases should I test for Maximum Score From Removing Substrings?
x == y: every removable pair is worth the same; Removing one pair glues its neighbours together and can create a new pair; Letters other than 'a' and 'b' act as walls that no pair can cross; No 'a' or no 'b' at all: the answer is 0.