aboutsummaryrefslogtreecommitdiff
path: root/max_score_removing_substr.py
blob: d76cf8c2dd62700d0a69c2b299a4c2e3d74e66cd (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 1717. Maximum Score From Removing Substrings
from collections import Counter

"""
given a sting '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.
remove substring "ba" and gain 'y' points. return the maximum points you can
gain after applying the above operations on 's'
"""


class Solution(object):
    def maximumGain(self, s, x, y):
        """
        :type s: str
        :type x: int
        :type y: int
        :rtype: int
        """
        a, b = "a", "b"
        if x < y:
            x, y = y, x
            a, b = b, a
        seen, ans = Counter(), 0
        for c in s + "x":
            if c in "ab":
                if c == b and 0 < seen[a]:
                    ans += x
                    seen[a] -= 1
                else:
                    seen[c] += 1
            else:
                ans += y * min(seen[a], seen[b])
                seen = Counter()
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.maximumGain(s="cdbcbbaaabab", x=4, y=5))
    print(obj.maximumGain(s="aabbaaxybbaabb", x=5, y=4))