Ones and zeroes

Array String Dynamic Programming

53.1% acceptance

Jan 13, 2026

6064

508

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn find_max_form(strs: Vec<String>, m: i32, n: i32) -> i32 {
    let (m, n) = (m as usize, n as usize);
    let mut dp = vec![vec![0; n + 1]; m + 1];
    
    for s in strs {
      let zeros = s.chars().filter(|&c| c == '0').count();
      let ones = s.len() - zeros;
      
      for i in (zeros..=m).rev() {
        for j in (ones..=n).rev() {
          dp[i][j] = dp[i][j].max(dp[i - zeros][j - ones] + 1);
        }
      }
    }
    
    dp[m][n]
  }
}