1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/**
 * Find the maximum size of the subset with at most m 0's and n 1's.
 * 3D Dynamic Programming approach.
 *
 * @param {string[]} strs - Array of binary strings
 * @param {number} m - Maximum number of 0's allowed
 * @param {number} n - Maximum number of 1's allowed
 * @return {number} - Maximum size of the subset
 */
function findMaxForm(strs, m, n) {
  const len = strs.length;
 
  // Count the number of 0's and 1's in each string
  const zeros = new Array(len);
  const ones = new Array(len);
 
  for (let i = 0; i < len; i++) {
    zeros[i] = 0;
    ones[i] = 0;
 
    for (let j = 0; j < strs[i].length; j++) {
      if (strs[i][j] === '0') {
        zeros[i]++;
      } else {
        ones[i]++;
      }
    }
  }
 
  // Initialize 3D DP array
  const dp = Array(len + 1).fill().map(() =>
    Array(m + 1).fill().map(() =>
      Array(n + 1).fill(0)
    )
  );
 
  for (let i = 1; i <= len; i++) {
    const zero = zeros[i - 1];
    const one = ones[i - 1];
 
    for (let j = 0; j <= m; j++) {
      for (let k = 0; k <= n; k++) {
        // Exclude the string
        dp[i][j][k] = dp[i - 1][j][k];
 
        // Include the string if we have enough capacity
        if (j >= zero && k >= one) {
          dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j - zero][k - one] + 1);
        }
      }
    }
  }
 
  return dp[len][m][n];
}
 
/**
 * Find the maximum size of the subset with at most m 0's and n 1's.
 * 2D Dynamic Programming approach (Space Optimization).
 *
 * @param {string[]} strs - Array of binary strings
 * @param {number} m - Maximum number of 0's allowed
 * @param {number} n - Maximum number of 1's allowed
 * @return {number} - Maximum size of the subset
 */
function findMaxFormOptimized(strs, m, n) {
  // Initialize 2D DP array
  const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
 
  for (const str of strs) {
    // Count the number of 0's and 1's in the current string
    let zero = 0;
    let one = 0;
 
    for (let i = 0; i < str.length; i++) {
      if (str[i] === '0') {
        zero++;
      } else {
        one++;
      }
    }
 
    // Update DP array in reverse order
    for (let j = m; j >= zero; j--) {
      for (let k = n; k >= one; k--) {
        dp[j][k] = Math.max(dp[j][k], dp[j - zero][k - one] + 1);
      }
    }
  }
 
  return dp[m][n];
}
 
// Test cases
console.log(findMaxForm(["10", "0001", "111001", "1", "0"], 5, 3));  // 4
console.log(findMaxForm(["10", "0", "1"], 1, 1));  // 2
 
console.log(findMaxFormOptimized(["10", "0001", "111001", "1", "0"], 5, 3));  // 4
console.log(findMaxFormOptimized(["10", "0", "1"], 1, 1));  // 2