DSA problem
Maximum Score From Removing Substrings
You are given a string s and two integers x and y. You can perform two types of operations any number of times. Remove substring "ab" and gain x points (only possible if "ab" is a substring of s), or remove substring "ba" and gain y points (only possible if "ba" is a substring of s). Return the maximum points you can gain after applying the above operations on s.
A search over the order of removals is exponential in the number of operations, so brute force is out of the question. The key observation is that within a maximal run of 'a's and 'b's (any letter outside {a, b} acts as a hard barrier), every "ab" removal and every "ba" removal both reduce the count of as and bs by exactly one each. So the only thing that varies between strategies is how many of each removal type we perform.
This gives the greedy structure: always prefer the higher-paying removal type. If x >= y, sweep the string and pop "ab" pairs first; then run a second sweep for "ba". Each sweep is naturally implemented with a stack: push the current character; if the top two characters form the high-paying pattern, pop both and add the points. After exhausting the high-paying pattern, repeat for the low-paying one on the residual string.
This works because once the higher-paying pattern is fully exhausted, no future removal can recreate it inside the same alternating run — the remaining letters all share the same first letter of the second pattern. Total time is O(n) over the two stack sweeps, and total space is O(n) for the stack.
Examples
s = "cdbcbbaaabab", x = 4, y = 519s = "aabbaaxybbaabb", x = 5, y = 420s = "abba", x = 7, y = 714Constraints
- 1 <= s.length <= 10^5
- 1 <= x, y <= 10^4
- s consists of lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.