101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 2 main approaches to solve this problem:

  1. 3D Dynamic Programming - Complex approach
  2. 2D Dynamic Programming (Space Optimization) - Complex approach

Approach 1: 3D Dynamic Programming

The key insight for solving this problem is to recognize it as a variation of the 0/1 Knapsack problem with two constraints: the number of 0's and the number of 1's.

Let's define dp[i][j][k] as the maximum size of the subset we can form using the first i strings, with at most j 0's and k 1's.

For each string, we have two options:

  1. Include the string in our subset.
  2. Exclude the string from our subset.

If we include the string, we need to ensure that we have enough capacity for its 0's and 1's. The recurrence relation is:

dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-zeros][k-ones] + 1) if j >= zeros and k >= ones

where zeros and ones are the number of 0's and 1's in the i-th string.

If we exclude the string, the recurrence relation is:

dp[i][j][k] = dp[i-1][j][k]

The final answer is dp[n][m][n], where n is the number of strings.

Algorithm:

  1. Count the number of 0's and 1's in each string and store them in arrays zeros and ones.
  2. Initialize a 3D DP array dp of size (n+1) x (m+1) x (n+1), where n is the number of strings.
  3. Set dp[0][j][k] = 0 for all j and k (base case: no strings selected).
  4. For each string i from 1 to n:
  5. a. For each j from 0 to m:
  6. i. For each k from 0 to n:
  7. 1. Exclude the string: dp[i][j][k] = dp[i-1][j][k]
  8. 2. Include the string if we have enough capacity: if j >= zeros[i-1] and k >= ones[i-1], dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-zeros[i-1]][k-ones[i-1]] + 1)
  9. Return dp[n][m][n] as the maximum size of the subset.

Time Complexity:

O(n * m * n)

Where n is the number of strings and m is the maximum number of 0's allowed. We need to compute dp[i][j][k] for each i from 0 to n, each j from 0 to m, and each k from 0 to n.

Space Complexity:

O(n * m * n)

We use a 3D DP array of size (n+1) x (m+1) x (n+1).

Approach 2: 2D Dynamic Programming (Space Optimization)

We can optimize the space complexity of the previous approach by observing that to calculate dp[i][j][k], we only need the values from dp[i-1][j][k].

Instead of using a 3D array, we can use a 2D array dp[j][k] to represent the maximum size of the subset we can form with at most j 0's and k 1's.

For each string, we update the DP array in reverse order to avoid using the updated values in the same iteration.

The recurrence relation becomes:

dp[j][k] = max(dp[j][k], dp[j-zeros][k-ones] + 1) if j >= zeros and k >= ones

This reduces the space complexity from O(n * m * n) to O(m * n).

Algorithm:

  1. Count the number of 0's and 1's in each string and store them in arrays zeros and ones.
  2. Initialize a 2D DP array dp of size (m+1) x (n+1), where m is the maximum number of 0's allowed and n is the maximum number of 1's allowed.
  3. Set dp[j][k] = 0 for all j and k (base case: no strings selected).
  4. For each string i from 0 to n-1:
  5. a. For each j from m down to zeros[i]:
  6. i. For each k from n down to ones[i]:
  7. 1. Update dp[j][k] = max(dp[j][k], dp[j-zeros[i]][k-ones[i]] + 1)
  8. Return dp[m][n] as the maximum size of the subset.

Time Complexity:

O(n * m * n)

Where n is the number of strings and m is the maximum number of 0's allowed. We need to compute dp[j][k] for each string, each j from zeros[i] to m, and each k from ones[i] to n.

Space Complexity:

O(m * n)

We use a 2D DP array of size (m+1) x (n+1).

Pseudocode

solution.pseudo
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
function findMaxForm(strs, m, n):
    // Count the number of 0's and 1's in each string
    zeros = new array of size strs.length
    ones = new array of size strs.length
 
    for i from 0 to strs.length - 1:
        for char in strs[i]:
            if char == '0':
                zeros[i]++
            else:
                ones[i]++
 
    // Initialize 3D DP array
    dp = new 3D array of size (strs.length + 1) x (m + 1) x (n + 1), initialized with 0
 
    for i from 1 to strs.length:
        for j from 0 to m:
            for k from 0 to n:
                // Exclude the string
                dp[i][j][k] = dp[i - 1][j][k]
 
                // Include the string if we have enough capacity
                if j >= zeros[i - 1] and k >= ones[i - 1]:
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - zeros[i - 1]][k - ones[i - 1]] + 1)
 
    return dp[strs.length][m][n]
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone