Maximum Score From Removing Substrings: Greedy Stack Pattern

You are given a string s and two integers x and y. You can repeatedly remove the substring "ab" and gain x points, or remove the substring "ba" and gain y points. You want to maximize your total score by choosing the order of removals optimally.

This is LeetCode 1717: Maximum Score From Removing Substrings, a medium problem that tests your ability to combine greedy reasoning with stack-based string processing. The trick is figuring out which pair to remove first, and then using a stack to remove all instances efficiently.

Why this problem matters

At first, this looks like it might require dynamic programming or backtracking to explore all possible removal orders. But the structure of the problem allows a much simpler approach. The two substrings "ab" and "ba" compete for the same characters (a's and b's), so removing one type of pair can prevent certain pairs of the other type from forming. This means the order you process them in affects the total score.

This problem teaches a pattern that shows up across many greedy and stack problems: when two operations compete for the same resources, process the more valuable one first. You will see this principle in scheduling problems, resource allocation, and other optimization tasks.

The stack-based removal technique itself is broadly useful. Any time you need to scan a string and collapse adjacent pairs or patterns, a stack gives you O(n) performance without needing to actually modify the string repeatedly.

The key insight

The greedy principle here is simple: always remove the higher-scoring pair first. If x >= y, remove all "ab" pairs before touching any "ba" pairs. If y > x, do the reverse.

Why does this work? Both "ab" and "ba" compete for the same pool of a and b characters. Removing an "ab" pair consumes one a and one b, which might have otherwise formed a "ba" pair (and vice versa). Since the pairs share resources, you want the more valuable operation to get first pick of the available characters. Whatever is left over goes to the lower-scoring operation.

The stack makes the removal efficient. Instead of repeatedly scanning the string to find and remove pairs (which would be O(n^2) in the worst case), you push characters onto a stack one by one. Whenever the top of the stack and the current character form the target pair, you pop the stack and add points. After one pass, the stack contains the string with all instances of that pair removed.

Walking through it step by step

Let's trace through s = "cabxbae" with x = 5 (for "ab") and y = 3 (for "ba").

The greedy ordering ensured we got 5 points from the "ab" pair before the "ba" pass claimed any a or b characters. If we had removed "ba" first, we might have consumed characters that could have formed higher-value "ab" pairs instead.

The solution

def maximum_gain(s: str, x: int, y: int) -> int:
    if x < y:
        s = s[::-1]
        x, y = y, x

    def remove_pair(chars, first, second, points):
        stack = []
        score = 0
        for c in chars:
            if stack and stack[-1] == first and c == second:
                stack.pop()
                score += points
            else:
                stack.append(c)
        return stack, score

    remaining, score1 = remove_pair(s, 'a', 'b', x)
    _, score2 = remove_pair(remaining, 'b', 'a', y)

    return score1 + score2

Here is what each piece does:

1. Normalize the order. If y > x, reverse the string and swap the scores. Reversing the string turns every "ba" into an "ab" and vice versa. This lets us always process "ab" first without writing two separate code paths.
2. First pass with remove_pair. Scan through the string, pushing characters onto a stack. Whenever the stack top is 'a' and the current character is 'b', pop the 'a' and add x points. The stack holds the remaining characters after all "ab" pairs are removed.
3. Second pass. Feed the remaining characters (from the stack) into remove_pair again, this time looking for 'b' followed by 'a'. Add y points for each match.
4. Return the combined score.

The remove_pair function is a reusable building block. It takes any sequence of characters, a target pair (first, second), and a point value, then removes all adjacent instances of that pair using a stack. This same function works for both passes, just with different parameters.

Complexity analysis

Each character is pushed onto and popped from the stack at most once per pass. The first pass processes n characters, and the second pass processes whatever remains (at most n characters). The total work is proportional to n.

The stack can hold up to n characters in the worst case (when no pairs are found), so space is O(n). If you want to be precise, the second pass uses a second stack, but its size is bounded by n as well, so the overall space remains O(n).

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Stack-based substring removal

The pattern of using a stack to remove adjacent pairs from a string in a single pass:

def remove_adjacent(chars, first, second):
    stack = []
    for c in chars:
        if stack and stack[-1] == first and c == second:
            stack.pop()
        else:
            stack.append(c)
    return stack

This is the same core mechanic used in "Remove All Adjacent Duplicates in String" (LeetCode 1047) and its follow-up (LeetCode 1209). Instead of checking for duplicate characters, you check for a specific two-character pattern. The stack naturally handles cascading removals: when you remove a pair, the characters on either side of it become adjacent and might form a new pair on the next iteration.

2. Greedy ordering principle

The pattern of processing the more valuable operation first when two operations compete for shared resources:

if value_a >= value_b:
    process_a_first()
    process_b_second()
else:
    process_b_first()
    process_a_second()

This appears in scheduling problems (process the highest-value job first), in coin change problems (greedy denomination selection), and in any scenario where you have limited resources and want to maximize total value. The key requirement is that the operations must be independent enough that order does not affect the total number of operations, only their distribution between the two types.

Edge cases

Before submitting, make sure your solution handles these:

• String with no a or b characters like s = "xyz": no pairs can be removed, so the score is 0. The stack passes through cleanly with no pops.
• All characters form one pair type like s = "ababab" with x = 5, y = 3: the first pass removes all three "ab" pairs for 15 points, and the second pass has nothing left to remove.
• x equals y: the order does not matter. Both orderings produce the same total score.
• Single character or empty string: no pairs can form, score is 0.
• Nested patterns like s = "aabb": the stack processes this as a, a, b (pop a, score), then b (pop a, score). Both "ab" pairs are removed, scoring 10 if x = 5.
• Long alternating sequences like s = "abababab": each "ab" is removed in sequence. The stack handles this in one pass without issues.

From understanding to recall

You have read through the greedy stack approach, and it makes sense. Check which pair scores higher, remove those first with a stack, then remove the other pair from whatever remains. Two passes, two stack scans, done.

But in an interview, it is easy to second-guess the greedy choice. Should you really always remove the higher-scoring pair first? What about cases where removing a lower-scoring pair now creates more higher-scoring pairs later? (It does not, but under pressure, you might not be sure.) And the string reversal trick for normalizing the order is easy to forget when you are writing code from scratch.

Spaced repetition fixes this. You practice the greedy ordering decision, the stack removal loop, and the normalization trick at increasing intervals. After a few rounds, the pattern is automatic. You see "two competing substring removals" and you immediately know: sort by value, process the expensive one first, use a stack for each pass.

The greedy-plus-stack combination is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Remove All Adjacent Duplicates in String II - Stack-based adjacent removal with a count threshold
• Remove Duplicate Letters - Greedy stack approach to build optimal strings
• Daily Temperatures - Monotonic stack pattern for processing sequences

CodeBricks breaks the maximum score from removing substrings LeetCode problem into its stack-based removal and greedy ordering building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy stack question shows up in your interview, you do not think about it. You just write it.