1115MediumStringStackGreedy

Pulling Pairs Off the Tape

Tracked in this browser only

Trains the technique from

LeetCode 1717Maximum Score From Removing Substrings

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A tape tape holds lowercase letters. Two moves are allowed, each usable as often as the pattern shows up:

Pull out a neighbouring pair reading ab and collect x points.
Pull out a neighbouring pair reading ba and collect y points.

Pulling a pair out closes the gap, so letters that were apart may become neighbours.

Return the most points that can be collected.

Examples

Example 1

Input: tape = "aba", x = 1, y = 5
Output: 5

Only one pull is ever possible. Taking ba from the back pays 5, while taking ab from the front would pay 1.

Example 2

Input: tape = "bbba", x = 5, y = 1
Output: 1

The only pair on offer reads ba and pays 1. Once it is gone the tape reads bb with nothing left to pull.

Example 3

Input: tape = "abcba", x = 5, y = 1
Output: 6

The c splits the tape in two. On the left ab pays 5 and on the right ba pays 1.

Constraints

1 <= tape.length <= 10^5
1 <= x <= 10^4
1 <= y <= 10^4
tape holds only lowercase English letters

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def maximum_gain(tape: str, x: int, y: int) -> int:

Java

public int maximumGain(String tape, int x, int y)

The intended approach

Time O(n) over the tape.Space O(1) for the two counters.

Any letter other than `a` or `b` can never be pulled out and never becomes a neighbour of anything across itself, so it splits the tape into stretches that are handled quite separately. Within a stretch, taking the better-paying pair as often as possible first is never a mistake. Whenever both patterns are available they overlap in at most one letter, and choosing the better-paying one first leaves the other still takeable wherever it mattered, so no worse-paying pull is ever forced by going in that order. One counter carries out the better-paying pass. Say the better pair is `ab`: count the `a` letters waiting, and each `b` either cancels a waiting `a` for the higher payout or, if none waits, joins a tally of leftover `b` letters. Once the stretch is done, the leftovers are every `b` that found no `a` followed by every `a` that found no `b`, which reads as a block of `b` then a block of `a`. The worse-paying pull applies to that shape as many times as the smaller of the two tallies. Reset both counters at each splitting letter and settle the leftovers there.

Pythonentry point: maximum_gain

def maximum_gain(tape, x, y):
    if x >= y:
        lead = "a"
        follow = "b"
        high = x
        rest = y
    else:
        lead = "b"
        follow = "a"
        high = y
        rest = x
    total = 0
    waiting = 0
    spare = 0
    for ch in tape:
        if ch == lead:
            waiting += 1
        elif ch == follow:
            if waiting:
                waiting -= 1
                total += high
            else:
                spare += 1
        else:
            total += rest * (waiting if waiting < spare else spare)
            waiting = 0
            spare = 0
    total += rest * (waiting if waiting < spare else spare)
    return total

The obvious version

Try every pull. From a tape, look at each neighbouring pair, and for the ones reading `ab` or `ba` take that payout plus the best from the shorter tape left behind, keeping the largest. Tapes already worked out are remembered so the same one is never redone.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_maximum_gain(tape, x, y):
    known = {}

    def solve(text):
        if text in known:
            return known[text]
        top = 0
        for i in range(len(text) - 1):
            pair = text[i:i + 2]
            if pair == "ab":
                got = x + solve(text[:i] + text[i + 2:])
                if got > top:
                    top = got
            elif pair == "ba":
                got = y + solve(text[:i] + text[i + 2:])
                if got > top:
                    top = got
        known[text] = top
        return top

    return solve(tape)

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in