leetcode

commit e8467a9e01906a03a1ecb58ae70f9af7dbd1e1ba
parent b625f10863beea22bfd39f94a1858c0d85e0f355
Author: Jack Sangdahl <jack@pngu.org>
Date:   Mon, 10 Nov 2025 21:30:48 -0700

474. ones and zeroes

Diffstat:
A
ones_and_zeroes.c
 | 
38
++++++++++++++++++++++++++++++++++++++
A
ones_and_zeroes.py
 | 
43
+++++++++++++++++++++++++++++++++++++++++++

2 files changed, 81 insertions(+), 0 deletions(-)
diff --git a/ones_and_zeroes.c b/ones_and_zeroes.c
@@ -0,0 +1,38 @@
+// 474. Ones and Zeroes
+#include "leetcode.h"
+
+/*
+ * you are given an array of binary strings 'strs', and two integers 'm' and
+ * 'n'. return the size of the largest subset of 'strs' such that there are at
+ * most 'm' 0's and 'n' 1's in the subset. a set 'x' is a subset of a set 'y' if
+ * all elements of 'x' are also elements of 'y'.
+ */
+
+int findMaxForm(char **strs, int strsSize, int m, int n) {
+  int *dp = (int *)calloc((m + 1) * (n + 1), sizeof(int));
+  for (int i = 0; i < strsSize; i++) {
+    int zeroes = 0, ones = 0;
+    for (int j = 0; strs[i][j]; ++j) {
+      if (strs[i][j] == '0')
+        zeroes++;
+      else
+        ones++;
+    }
+    for (int j = m; j >= zeroes; --j)
+      for (int k = n; k >= ones; --k) {
+        int idx = j * (n + 1) + k;
+        int prev = (j - zeroes) * (n + 1) + (k - ones);
+        if (dp[idx] < dp[prev] + 1)
+          dp[idx] = dp[prev] + 1;
+      }
+  }
+  int ans = dp[m * (n + 1) + n];
+  free(dp);
+  return ans;
+}
+
+int main() {
+  char *s1[] = {"10", "0001", "111001", "1", "0"}, *s2[] = {"10", "0", "1"};
+  printf("%d\n", findMaxForm(s1, ARRAY_SIZE(s1), 5, 3)); // expect: 4
+  printf("%d\n", findMaxForm(s2, ARRAY_SIZE(s2), 1, 1)); // expect: 2
+}
diff --git a/ones_and_zeroes.py b/ones_and_zeroes.py
@@ -0,0 +1,43 @@
+# 474. Ones and Zeroes
+
+"""
+you are given an array of binary strings 'strs', and two integers 'm' and
+'n'. return the size of the largest subset of 'strs' such that there are at
+most 'm' 0's and 'n' 1's in the subset. a set 'x' is a subset of a set 'y' if
+all elements of 'x' are also elements of 'y'.
+"""
+
+
+class Solution(object):
+    def findMaxForm(self, strs, m, n):
+        """
+        :type strs: List[str]
+        :type m: int
+        :type n: int
+        :rtype: int
+        """
+        dp = {(0, 0): 0}
+        for i in strs:
+            ones, zeroes = 0, 0
+            for j in i:
+                if j == "0":
+                    zeroes += 1
+                else:
+                    ones += 1
+            tmp = {}
+            for k, v in dp.items():
+                prev_zeroes, prev_ones = k
+                new_zeroes, new_ones = prev_zeroes + zeroes, prev_ones + ones
+                if new_zeroes <= m and new_ones <= n:
+                    if (new_zeroes, new_ones) not in dp:
+                        tmp[(new_zeroes, new_ones)] = v + 1
+                    elif dp[(new_zeroes, new_ones)] < v + 1:
+                        tmp[(new_zeroes, new_ones)] = v + 1
+            dp.update(tmp)
+        return max(dp.values())
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.findMaxForm(strs=["10", "0001", "111001", "1", "0"], m=5, n=3))
+    print(obj.findMaxForm(strs=["10", "0", "1"], m=1, n=1))