Maximum Score From Removing Substrings — Problem & Solution
Maximum Score From Removing Substrings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Score From Removing Substrings is a medium coding problem on strings, greedy and stack, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Greedy, Stack
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string s and two integers x and y. You may repeatedly:
- remove the substring
"ab"and gainxpoints, or - remove the substring
"ba"and gainypoints.
Return the maximum total score obtainable.
Example 1
Input: s = "cdbcbbaaabab", x = 4, y = 5
Output: 19
Example 2
Input: s = "aabbaaxybbaabb", x = 5, y = 4
Output: 20
Example 3
Input: s = "ab", x = 1, y = 10
Output: 1
Constraints
1 <= s.length <= 401 <= x, y <= 10000s consists of lowercase English letters.
Hints for Maximum Score From Removing Substrings
Hint 1
Removing the higher-scoring pair first is never worse — any
abandbathat compete for the same letters can be reordered without loss.Hint 2
So sweep once with a stack removing the better pair, then sweep the leftover string removing the other.
Hint 3
Letters that are neither
anorbsimply block matches and stay on the stack.
How to solve Maximum Score From Removing Substrings
Remove the higher-scoring pair greedily first with a stack, then sweep the leftover removing the other pair.
Approach
- Pick
firstas the pair with the larger score. - Sweep
swith a stack popping and scoring whenevertop + ch == first. - Sweep the remaining string the same way for the other pair.
Why it works
Whenever an ab and a ba compete for the same letters, taking the more valuable one never reduces the total number of pairs removable, so greedy by value is optimal; each sweep removes every pair reachable after cancellations.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Letters other than
a/bstay on the stack and separate segments.
Reference solution
Python
def maximumGain(s: str, x: int, y: int) -> int:
first = "ab" if x >= y else "ba"
second = "ba" if x >= y else "ab"
total = 0
def sweep(text, pair, score):
nonlocal total
stack = []
for ch in text:
if stack and stack[-1] == pair[0] and ch == pair[1]:
stack.pop()
total += score
else:
stack.append(ch)
return "".join(stack)
rest = sweep(s, first, max(x, y))
sweep(rest, second, min(x, y))
return totalJava
private static int gainTotal;
private static String gainSweep(String text, char first, char second, int score) {
StringBuilder stack = new StringBuilder();
for (int i = 0; i < text.length(); i++) {
char c = text.charAt(i);
if (stack.length() > 0 && stack.charAt(stack.length() - 1) == first && c == second) {
stack.deleteCharAt(stack.length() - 1);
gainTotal += score;
} else {
stack.append(c);
}
}
return stack.toString();
}
public static int maximumGain(String s, int x, int y) {
gainTotal = 0;
if (x >= y) {
String rest = gainSweep(s, 'a', 'b', x);
gainSweep(rest, 'b', 'a', y);
} else {
String rest = gainSweep(s, 'b', 'a', y);
gainSweep(rest, 'a', 'b', x);
}
return gainTotal;
}C++
static int gainTotal;
static string gainSweep(const string& text, char first, char second, int score) {
string stk;
for (char c : text) {
if (!stk.empty() && stk.back() == first && c == second) {
stk.pop_back();
gainTotal += score;
} else {
stk.push_back(c);
}
}
return stk;
}
int maximumGain(string s, int x, int y) {
gainTotal = 0;
if (x >= y) {
string rest = gainSweep(s, 'a', 'b', x);
gainSweep(rest, 'b', 'a', y);
} else {
string rest = gainSweep(s, 'b', 'a', y);
gainSweep(rest, 'a', 'b', x);
}
return gainTotal;
}JavaScript
var maximumGain = function(s, x, y) {
const first = x >= y ? "ab" : "ba";
const second = x >= y ? "ba" : "ab";
let total = 0;
const sweep = function(input, pair, score) {
const stack = [];
for (let i = 0; i < input.length; i++) {
if (stack.length > 0 && stack[stack.length - 1] === pair.charAt(0) && input.charAt(i) === pair.charAt(1)) {
stack.pop();
total += score;
} else {
stack.push(input.charAt(i));
}
}
return stack.join("");
};
const rest = sweep(s, first, Math.max(x, y));
sweep(rest, second, Math.min(x, y));
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Greedy Algorithms