diff options
author | Jack Sangdahl <[email protected]> | 2024-10-06 21:57:34 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-10-06 21:58:06 -0600 |
commit | e4e9e626e5b5a9659510d4b71a742f14e4580079 (patch) | |
tree | c91e9a9240f36edd9efb7fb0c2846abf3d5222fb | |
parent | 071f544d646729018aeba458dd7fa8e20f71d58a (diff) | |
download | leetcode-e4e9e626e5b5a9659510d4b71a742f14e4580079.tar.gz leetcode-e4e9e626e5b5a9659510d4b71a742f14e4580079.zip |
2696. minimum string legnth after removing substrings
-rw-r--r-- | min_string_len_remove_substr.c | 33 | ||||
-rw-r--r-- | min_string_len_remove_substr.py | 36 |
2 files changed, 69 insertions, 0 deletions
diff --git a/min_string_len_remove_substr.c b/min_string_len_remove_substr.c new file mode 100644 index 0000000..4d0ed57 --- /dev/null +++ b/min_string_len_remove_substr.c @@ -0,0 +1,33 @@ +// 2696. Minimum String Length After Removing Substrings +#include "leetcode.h" + +/* + * you are given a string 's' consisting only of uppercase english letters. you + * can apply some operations to this string where in one operation you can + * remove any occurence of one of the sbustrings 'AB' or 'CD' from 's'. return + * the minimum possible length of the resulting string that you can obtain. note + * that the string concatenates after removing the substring and could produce + * new 'AB' or 'CD' substrings + */ + +int minLength(char *s) { + int n = strlen(s), top = -1, ans; + char *stack = (char *)malloc((n + 1) * sizeof(char)); + for (int i = 0; i < n; i++) { + if (top >= 0 && + (stack[top] == 'A' && s[i] == 'B' || stack[top] == 'C' && s[i] == 'D')) + top--; + else + stack[++top] = s[i]; + } + stack[++top] = '\0'; + ans = top; + free(stack); + return ans; +} + +int main() { + char *s1 = "ABFCACDB", *s2 = "ACBBD"; + printf("%d\n", minLength(s1)); // expect: 2 + printf("%d\n", minLength(s2)); // expect: 5 +} diff --git a/min_string_len_remove_substr.py b/min_string_len_remove_substr.py new file mode 100644 index 0000000..89d2190 --- /dev/null +++ b/min_string_len_remove_substr.py @@ -0,0 +1,36 @@ +# 2696. Minimum String Length After Removing Substrings + +""" +you are given a string 's' consisting only of uppercase english letters. you +can apply some operations to this string where in one operation you can +remove any occurence of one of the sbustrings 'AB' or 'CD' from 's'. return +the minimum possible length of the resulting string that you can obtain. note +that the string concatenates after removing the substring and could produce +new 'AB' or 'CD' substrings +""" + + +class Solution(object): + def minLength(self, s): + """ + :type s: str + :rtype: int + """ + stack = [] + for c in s: + if not stack: + stack.append(c) + continue + if c == "B" and stack[-1] == "A": + stack.pop() + elif c == "D" and stack[-1] == "C": + stack.pop() + else: + stack.append(c) + return len(stack) + + +if __name__ == "__main__": + obj = Solution() + print(obj.minLength(s="ABFCACDB")) + print(obj.minLength(s="ACBBD")) |