Ones and Zeroes Easy 0 attempts
LeetCode ↗

Ones and Zeroes

Easy Dynamic ProgrammingMemoization LeetCode

You're given an array strs of binary strings, along with two limits, m and n. Choose as many strings from strs as you can, using each at most once, such that across all the chosen strings there are no more than m '0's and no more than n '1's combined. Return the largest number of strings you can select under that budget.

Input Format
Implement findMaxForm(strs, m, n). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
strs = ["10","0001","111001","1","0"]
m = 5
n = 3
Output
4

Example 2

Input
strs = ["0","0","1"]
m = 1
n = 1
Output
2
Constraints
  • 1 <= strs.length <= 600
  • 1 <= strs[i].length <= 100
  • 1 <= m, n <= 100
Test Cases (2)
Case 1
Args: [["10","0001","111001","1","0"],5,3] Expected: 4
Case 2
Args: [["0","0","1"],1,1] Expected: 2
Topics
Dynamic ProgrammingMemoization

2D Knapsack DP

javascript
function findMaxForm(strs, m, n) {
  const dp = Array.from({length: m+1}, () => Array(n+1).fill(0));
  for (const s of strs) {
    const zeros = [...s].filter(c => c==='0').length;
    const ones = s.length - zeros;
    for (let i = m; i >= zeros; i--)
      for (let j = n; j >= ones; j--)
        dp[i][j] = Math.max(dp[i][j], dp[i-zeros][j-ones] + 1);
  }
  return dp[m][n];
}

Time: O(C + S × m × n), where C is total input characters and S is the number of strings | Space: O(m × n)

Saved in this browser only. Private to you.

JavaScript