Skip to content

1717. Maximum Score From Removing Substrings

Difficulty Topics

Description

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.
    • For example, when removing "ab" from "cabxbae" it becomes "cxbae".
  • Remove substring "ba" and gain y points.
    • For example, when removing "ba" from "cabxbae" it becomes "cabxe".

Return the maximum points you can gain after applying the above operations on s.

 

Example 1:

Input: s = "cdbcbbaaabab", x = 4, y = 5
Output: 19
Explanation:
- Remove the "ba" underlined in "cdbcbbaaabab". Now, s = "cdbcbbaaab" and 5 points are added to the score.
- Remove the "ab" underlined in "cdbcbbaaab". Now, s = "cdbcbbaa" and 4 points are added to the score.
- Remove the "ba" underlined in "cdbcbbaa". Now, s = "cdbcba" and 5 points are added to the score.
- Remove the "ba" underlined in "cdbcba". Now, s = "cdbc" and 5 points are added to the score.
Total score = 5 + 4 + 5 + 5 = 19.

Example 2:

Input: s = "aabbaaxybbaabb", x = 5, y = 4
Output: 20

 

Constraints:

  • 1 <= s.length <= 105
  • 1 <= x, y <= 104
  • s consists of lowercase English letters.

Solution

maximum-score-from-removing-substrings.py
class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:

        def remove(s, target, val):
            st = []
            ret = 0
            for c in s:
                st.append(c)
                if len(st)>=2 and (st[-2],st[-1])==target:
                    st.pop()
                    st.pop()
                    ret+= val
            return st, ret
        if y > x:
            s, val1 = remove(s, ('b','a'), y)
            s, val2 = remove(s, ('a','b'), x)
            return val1+val2
        s, val1 = remove(s, ('a','b'), x)
        s, val2 = remove(s, ('b','a'), y)
        return val1+val2