Remove occurrences of two specific substrings from a string in an order that maximizes total score.
You are given a string made up of lowercase English letters and two integers representing the score for removing one substring and another score for removing the other substring.
You may repeatedly choose an occurrence of one of the two target substrings and delete it from the string. Each deletion adds the corresponding points to your total score. After a deletion, the remaining characters close up, and new removable occurrences may appear.
Your task is to determine the maximum total score you can obtain by removing substrings in an optimal order.
A common version of this problem involves the substrings "ab" and "ba", with scores x and y. The optimal strategy depends on removing the higher-value pair first whenever possible, then processing the remaining characters for the other pair.
Input Format
- A string
sconsisting of lowercase English letters. - Two non-negative integers
xandy. - In the common formulation,
xis the score for removing"ab"andyis the score for removing"ba".
Output Format
Return the maximum total score achievable after repeatedly removing valid substrings.
Constraints
1 <= s.length.- Scores are non-negative integers.
- The string contains lowercase English letters only.
- The exact operational limit is not critical for practice; a linear or near-linear solution is expected.
Example 1
Input
s = "cdbcbbaaabab", x = 4, y = 5
Output
19
Explanation
Remove "ba" for 5 points, then "ab" for 4 points, and continue until no more valid removals exist. The optimal sequence yields a total of 19.
Example 2
Input
s = "aabbaaxybbaabb", x = 5, y = 4
Output
20
Explanation
The best strategy is to remove the higher-scoring pair first wherever possible, then clean up the remaining pair type. One optimal total is 20.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.