diff options
-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")) |