aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--max_score_removing_substr.c42
-rw-r--r--max_score_removing_substr.py41
-rw-r--r--readme.md2
3 files changed, 85 insertions, 0 deletions
diff --git a/max_score_removing_substr.c b/max_score_removing_substr.c
new file mode 100644
index 0000000..f6ab060
--- /dev/null
+++ b/max_score_removing_substr.c
@@ -0,0 +1,42 @@
+// 1717. Maximum Score From Removing Substrings
+#include "leetcode.h"
+
+/*
+ * 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'
+ */
+
+int remove_pattern(char *s, const char *r, int x) {
+ int i = 0, res = 0, n = strlen(s);
+ for (int j = 0; j < n; ++j) {
+ s[i++] = s[j];
+ if (i > 1 && s[i - 2] == r[0] && s[i - 1] == r[1]) {
+ i -= 2;
+ res += x;
+ }
+ }
+ s[i] = '\0';
+ return res;
+}
+
+int maximumGain(char *s, int x, int y) {
+ char a[3] = "ab", b[3] = "ba";
+ if (x < y) {
+ char tmp[3];
+ strcpy(tmp, a);
+ strcpy(a, b);
+ strcpy(b, tmp);
+ int tmp_x = x;
+ x = y;
+ y = tmp_x;
+ }
+ return remove_pattern(s, a, x) + remove_pattern(s, b, y);
+}
+
+int main() {
+ char s1[] = "cdbcbbaaabab", s2[] = "aabbaaxybbaabb";
+ printf("%d\n", maximumGain(s1, 4, 5)); // expect: 19
+ printf("%d\n", maximumGain(s2, 5, 4)); // expect: 20
+}
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))
diff --git a/readme.md b/readme.md
index e080e67..5a802df 100644
--- a/readme.md
+++ b/readme.md
@@ -23,6 +23,7 @@ int res = func(arr, ARRAY_SIZE(arr));
returned by such functions. for example, see the following `main` functions.
**ListNode data type**
+
![image](https://assets.leetcode.com/uploads/2022/02/02/ex1-1.png)
```c
int main() {
@@ -41,6 +42,7 @@ int main() {
```
**TreeNode data type**
+
![image](https://assets.leetcode.com/uploads/2021/04/08/leftsum-tree.jpg)
```c
int main() {