diff options
-rw-r--r-- | max_score_removing_substr.c | 42 | ||||
-rw-r--r-- | max_score_removing_substr.py | 41 | ||||
-rw-r--r-- | readme.md | 2 |
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)) @@ -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** +  ```c int main() { @@ -41,6 +42,7 @@ int main() { ``` **TreeNode data type** +  ```c int main() { |