aboutsummaryrefslogtreecommitdiff
path: root/max_score_removing_substr.py
diff options
context:
space:
mode:
Diffstat (limited to 'max_score_removing_substr.py')
-rw-r--r--max_score_removing_substr.py41
1 files changed, 41 insertions, 0 deletions
diff --git a/max_score_removing_substr.py b/max_score_removing_substr.py
new file mode 100644
index 0000000..d76cf8c
--- /dev/null
+++ b/max_score_removing_substr.py
@@ -0,0 +1,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))