aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-10-06 21:57:34 -0600
committerJack Sangdahl <[email protected]>2024-10-06 21:58:06 -0600
commite4e9e626e5b5a9659510d4b71a742f14e4580079 (patch)
treec91e9a9240f36edd9efb7fb0c2846abf3d5222fb
parent071f544d646729018aeba458dd7fa8e20f71d58a (diff)
downloadleetcode-e4e9e626e5b5a9659510d4b71a742f14e4580079.tar.gz
leetcode-e4e9e626e5b5a9659510d4b71a742f14e4580079.zip
2696. minimum string legnth after removing substrings
-rw-r--r--min_string_len_remove_substr.c33
-rw-r--r--min_string_len_remove_substr.py36
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"))