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.
s consisting of lowercase English letters.x and y.x is the score for removing "ab" and y is the score for removing "ba".Return the maximum total score achievable after repeatedly removing valid substrings.
1 <= s.length.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
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.