aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--min_deletions_balance_str.c29
-rw-r--r--min_deletions_balance_str.py31
2 files changed, 60 insertions, 0 deletions
diff --git a/min_deletions_balance_str.c b/min_deletions_balance_str.c
new file mode 100644
index 0000000..6daeda1
--- /dev/null
+++ b/min_deletions_balance_str.c
@@ -0,0 +1,29 @@
+// 1653. Minimum Deletions to Make String Balanced
+#include "leetcode.h"
+
+/*
+ * you are given a string 's' consisting of only characters 'a' and 'b'. you can
+ * delete any number of characters in 's' to make 's' balanced. 's' is balanced
+ * if there is no pair of indices '(i, j)' such that 'i < j' and 's[i] = b' and
+ * 's[j] = a'. return the minimum number of deletions needed to make 's'
+ * balanced.
+ */
+
+int minimumDeletions(char *s) {
+ int cnt = 0, ans = 0;
+ for (int i = 0; s[i] != '\0'; i++) {
+ if (s[i] == 'b') {
+ cnt++;
+ } else if (cnt) {
+ ans++;
+ cnt--;
+ }
+ }
+ return ans;
+}
+
+int main() {
+ char *s1 = "aababbab", *s2 = "bbaaaaabb";
+ printf("%d\n", minimumDeletions(s1)); // expect: 2
+ printf("%d\n", minimumDeletions(s2)); // expect: 2
+}
diff --git a/min_deletions_balance_str.py b/min_deletions_balance_str.py
new file mode 100644
index 0000000..674b1aa
--- /dev/null
+++ b/min_deletions_balance_str.py
@@ -0,0 +1,31 @@
+# 1653. Minimum Deletions to Make String Balanced
+
+"""
+you are given a string 's' consisting of only characters 'a' and 'b'. you can
+delete any number of characters in 's' to make 's' balanced. 's' is balanced
+if there is no pair of indices '(i, j)' such that 'i < j' and 's[i] = b' and
+'s[j] = a'. return the minimum number of deletions needed to make 's'
+balanced.
+"""
+
+
+class Solution(object):
+ def minimumDeletions(self, s):
+ """
+ :type s: str
+ :rtype: int
+ """
+ a, b, cnt = s.count("a"), 0, len(s)
+ for c in s:
+ if c == "b":
+ cnt = min(cnt, a + b)
+ b += 1
+ else:
+ a -= 1
+ return min(cnt, b)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minimumDeletions("aababbab"))
+ print(obj.minimumDeletions("bbaaaaabb"))