Show problems as
Classic problem #1717MediumStringStackGreedy

Maximum Score From Removing Substrings

Real-world version: Pulling Pairs Off the Tape
Tracked in this browser only
Read Maximum Score From Removing Substrings on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def maximum_gain(tape: str, x: int, y: int) -> int:
Java
public int maximumGain(String tape, int x, int y)

More on the same topics