Maximum Score From Removing Substrings
MedPrompt
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 gainxpoints.- For example, when removing
"ab"from"cabxbae"it becomes"cxbae".
- For example, when removing
- Remove substring
"ba"and gainypoints.- 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 <= 1051 <= x, y <= 104sconsists of lowercase English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. It repeatedly scans the string to find and remove occurrences of "ab" or "ba", adding the corresponding points to a running total. The choice of which substring to remove at each step is made greedily based on which one offers more points.
Algorithm
- Initialize
totalScore = 0. - Start a loop that continues as long as removals are possible.
- Inside the loop, set a flag
found = false. - Determine which pair to prioritize. If
x > y, prioritize "ab". Otherwise, prioritize "ba". - Search for the high-priority pair (e.g., using
s.indexOf("ab")). - If found, remove it from the string, add its score to
totalScore, setfound = true, and continue to the next iteration of the loop. - If the high-priority pair is not found, search for the low-priority pair.
- If the low-priority pair is found, remove it, add its score, set
found = true, and continue. - If neither pair is found (
foundremainsfalse), break the loop. - Return
totalScore.
Walkthrough
The brute-force method involves iterating through the string in a loop. In each iteration, we search for the substrings "ab" and "ba". Based on the scores x and y, we decide which one to remove first. For instance, if x is greater than y, we prioritize finding and removing "ab". After a removal, the string is modified, and the process repeats from the beginning of the new, shorter string. This continues until no more "ab" or "ba" substrings can be found. While simple to conceptualize, this method is very slow because string search and modification operations inside a loop lead to a high time complexity.
Complexity
Time
O(N^2) or worse. In the worst case, we might perform O(N) removals, and each removal involves a string search and modification, which takes O(N) time.
Space
O(N), where N is the length of the string. A new string or `StringBuilder` is often created in each step of removal.
Trade-offs
Pros
Conceptually simple and easy to understand.
Cons
Extremely inefficient due to repeated string searching and manipulation.
Each removal operation on a string is costly, typically O(N).
Will result in a 'Time Limit Exceeded' error for the given constraints.
A more efficient approach is to use a greedy strategy. The key observation is that it's always optimal to prioritize removing the substring that yields a higher score. For example, if x > y, we should remove as many "ab"s as possible before considering "ba"s. This can be implemented in two passes. The first pass removes all instances of the higher-scoring pair, and the second pass removes all instances of the lower-scoring pair from the resulting string. A stack (or a StringBuilder used as a stack) is an effective tool for removing adjacent pairs in linear time.
Algorithm
- Compare
xandyto decide the priority. Let's sayx >= y. The high-priority pair is "ab" with scorex, and the low-priority is "ba" with scorey. - Define a helper function,
process(s, pair, score), that takes a string, a pair to remove (e.g., "ab"), and its score. - Inside
process, use a stack-like approach (e.g., aStringBuilder). Iterate through the input strings:- If the current character and the last character in the
StringBuilderform the targetpair, pop the last character and add thescoreto a running total for this pass. - Otherwise, append the current character to the
StringBuilder.
- If the current character and the last character in the
- The
processfunction returns the score gained and the resulting string (from theStringBuilder). - First Pass: Call
process(original_s, high_priority_pair, high_score). This will remove all high-priority pairs. Store the returned score and the new intermediate string. - Second Pass: Call
process(intermediate_string, low_priority_pair, low_score). This will remove all low-priority pairs from the result of the first pass. - The total maximum score is the sum of the scores from the two passes.
Walkthrough
This greedy approach is implemented with two main steps. First, we determine which pair, "ab" or "ba", has a higher score. Let's assume x >= y, making "ab" the high-priority pair.
We perform the first pass over the string s to remove all "ab"s. We can use a StringBuilder as a character stack. We iterate through s, and for each character, if it's a 'b' and the last character in our StringBuilder is an 'a', we've found an "ab" pair. We remove the 'a' from the StringBuilder and add x to our total score. Otherwise, we append the current character to the StringBuilder.
After the first pass, the StringBuilder contains a string with no "ab"s. We then perform a second pass on this new string to remove all "ba"s, adding y for each one found, using the same stack-based technique. The sum of scores from both passes gives the maximum possible score.
class Solution { public int maximumGain(String s, int x, int y) { if (x < y) { // Ensure x is always the score for the higher-priority pair int temp = x; x = y; y = temp; s = new StringBuilder(s).reverse().toString(); } long totalScore = 0; // First pass: remove "ab" (higher score) StringBuilder sb1 = new StringBuilder(); for (char c : s.toCharArray()) { if (c == 'b' && sb1.length() > 0 && sb1.charAt(sb1.length() - 1) == 'a') { sb1.deleteCharAt(sb1.length() - 1); totalScore += x; } else { sb1.append(c); } } // Second pass: remove "ba" (lower score) StringBuilder sb2 = new StringBuilder(); for (char c : sb1.toString().toCharArray()) { if (c == 'a' && sb2.length() > 0 && sb2.charAt(sb2.length() - 1) == 'b') { sb2.deleteCharAt(sb2.length() - 1); totalScore += y; } else { sb2.append(c); } } return (int) totalScore; }}Complexity
Time
O(N), as we iterate through the string a constant number of times (twice).
Space
O(N), where N is the length of the string. This space is used by the `StringBuilder`s to store the intermediate and final strings.
Trade-offs
Pros
Efficient with a linear time complexity.
Guaranteed to find the optimal solution due to the greedy strategy.
Passes the given constraints.
Cons
Requires O(N) extra space to hold the intermediate string and the stack used for processing.
This approach optimizes the two-pass method by eliminating the need for an intermediate string, thus reducing the space complexity to constant. It still follows the same greedy principle of prioritizing the higher-scoring pair. Instead of building a new string, we use counters to keep track of the available characters ('a's and 'b's) as we iterate through the string in a single pass. This allows us to calculate the score on the fly.
Algorithm
- Compare
xandyto determine the high-priority and low-priority pairs. Let's assumex >= y, so "ab" is high-priority. - Initialize
score = 0, and two counters,count1 = 0(for 'a') andcount2 = 0(for 'b'). - Iterate through the string
scharacter by character. - If the current character is the first character of the high-priority pair (e.g., 'a'), increment
count1. - If the current character is the second character of the high-priority pair (e.g., 'b'):
- If
count1 > 0, it means we can form a high-priority pair. Add the high score (x) toscoreand decrementcount1. - Otherwise, this character cannot form a high-priority pair. It might form a low-priority pair later. Increment
count2.
- If
- If the current character is neither 'a' nor 'b', it acts as a separator. The pending characters counted by
count1andcount2can no longer interact with characters that appear after the separator. The pending characters are effectively arranged such that allcount2characters appear before allcount1characters. Thus, they can formmin(count1, count2)low-priority pairs. Addmin(count1, count2) * low_scoretoscoreand reset both counters to 0. - After the loop finishes, there might be remaining characters counted in
count1andcount2. Perform the same calculation as in step 6: addmin(count1, count2) * low_scoretoscore. - If
y > xinitially, simply swap the roles of 'a' and 'b' andxandyin the logic above.
Walkthrough
We can achieve the same result as the two-pass approach in a single pass with constant extra space. The idea is to simulate the first pass (removing the high-priority pair) using a counter, and then calculate the score from the second pass based on the remaining characters.
Let's assume x >= y, so we prioritize removing "ab". We iterate through the string and maintain a count of available 'a's (countA). When we encounter a 'b', if countA > 0, we can form an "ab" pair. We add x to our score and decrement countA. If countA is 0, this 'b' cannot form an "ab" with a preceding 'a'. We keep track of these 'b's in a separate counter, countB.
Any character that is not 'a' or 'b' acts as a separator. When we encounter a separator, or at the very end of the string, the characters we've counted in countA and countB represent the leftovers from the first pass. These leftovers are effectively ordered with all 'b's before all 'a's (e.g., bbb...aaa...), so they can only form min(countA, countB) "ba" pairs. We add min(countA, countB) * y to the score and reset the counters when a separator is found.
This method avoids storing the intermediate string, making it the most optimal solution.
class Solution { public int maximumGain(String s, int x, int y) { if (x < y) { return maximumGain(new StringBuilder(s).reverse().toString(), y, x); } long score = 0; int countA = 0; int countB = 0; for (char c : s.toCharArray()) { if (c == 'a') { countA++; } else if (c == 'b') { if (countA > 0) { // Form "ab" score += x; countA--; } else { // Cannot form "ab", this 'b' might form "ba" later countB++; } } else { // Separator character // Process remaining 'a's and 'b's which can only form "ba" score += (long) Math.min(countA, countB) * y; countA = 0; countB = 0; } } // Process any remaining characters at the end of the string score += (long) Math.min(countA, countB) * y; return (int) score; }}Complexity
Time
O(N), as we iterate through the string only once.
Space
O(1), as we only use a few variables to store counters and the score.
Trade-offs
Pros
Most optimal solution with O(N) time and O(1) space complexity.
Processes the string in a single pass.
Cons
The logic can be slightly more complex to reason about compared to the direct simulation of the two-pass stack approach.
Solutions
Solution
class Solution {public int maximumGain(String s, int x, int y) { if (x < y) { return maximumGain(new StringBuilder(s).reverse().toString(), y, x); } int ans = 0; Deque<Character> stk1 = new ArrayDeque<>(); Deque<Character> stk2 = new ArrayDeque<>(); for (char c : s.toCharArray()) { if (c != 'b') { stk1.push(c); } else { if (!stk1.isEmpty() && stk1.peek() == 'a') { stk1.pop(); ans += x; } else { stk1.push(c); } } } while (!stk1.isEmpty()) { char c = stk1.pop(); if (c != 'b') { stk2.push(c); } else { if (!stk2.isEmpty() && stk2.peek() == 'a') { stk2.pop(); ans += y; } else { stk2.push(c); } } } return ans; }}function maximumGain ( s , x , y ) { let [ a , b ] = [ ' a ' , ' b ' ]; if ( x < y ) { [ x , y ] = [ y , x ]; [ a , b ] = [ b , a ]; } let [ ans , cnt1 , cnt2 ] = [ 0 , 0 , 0 ]; for ( let c of s ) { if ( c === a ) { cnt1 ++ ; } else if ( c === b ) { if ( cnt1 ) { ans += x ; cnt1 -- ; } else { cnt2 ++ ; } } else { ans += Math . min ( cnt1 , cnt2 ) * y ; cnt1 = 0 ; cnt2 = 0 ; } } ans += Math . min ( cnt1 , cnt2 ) * y ; return ans ; }class Solution {public: int maximumGain(string s, int x, int y) { if (x < y) { reverse(s.begin(), s.end()); return maximumGain(s, y, x); } int ans = 0; stack<char> stk1; stack<char> stk2; for (char c : s) { if (c != 'b') stk1.push(c); else { if (!stk1.empty() && stk1.top() == 'a') { stk1.pop(); ans += x; } else stk1.push(c); } } while (!stk1.empty()) { char c = stk1.top(); stk1.pop(); if (c != 'b') stk2.push(c); else { if (!stk2.empty() && stk2.top() == 'a') { stk2.pop(); ans += y; } else stk2.push(c); } } return ans; }};class Solution: def maximumGain(self, s: str, x: int, y: int) -> int: if x < y: return self . maximumGain(s[:: - 1], y, x) ans = 0 stk1, stk2 = [], [] for c in s: if c != 'b': stk1 . append(c) else: if stk1 and stk1[- 1] == 'a': stk1 . pop() ans += x else: stk1 . append(c) while stk1: c = stk1 . pop() if c != 'b': stk2 . append(c) else: if stk2 and stk2[- 1] == 'a': stk2 . pop() ans += y else: stk2 . append(c) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.