Scale Engineer

Ones and Zeroes

Med
#0461Time: O(2^L * S), where L is the length of `strs` and S is the maximum length of a string. For each of the `2^L` recursive paths, we may perform a count operation taking O(S) time. This is prohibitively slow for the given constraints.Space: O(L), where L is the length of `strs`. This space is used by the recursion stack.
Patterns
Dynamic Programming
Data structures
ArrayString

Prompt

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.

 

Example 1:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

Example 2:

Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: The largest subset is {"0", "1"}, so the answer is 2.

 

Constraints:

  • 1 <= strs.length <= 600
  • 1 <= strs[i].length <= 100
  • strs[i] consists only of digits '0' and '1'.
  • 1 <= m, n <= 100

Approaches

3 approaches with complexity analysis and trade-offs.

This approach explores all possible subsets of the given strings. For each string, we have two choices: either include it in our subset or not. This naturally leads to a recursive solution. We define a recursive function that tries both possibilities at each step, effectively traversing a binary decision tree.

Algorithm

  • Define a recursive function, say calculate(strs, index, zeros, ones), which computes the size of the largest subset from the subarray strs[index:] given the remaining capacity of zeros and ones.
  • For each string at strs[index], there are two choices:
    1. Exclude strs[index]: Recursively call calculate(strs, index + 1, zeros, ones).
    2. Include strs[index]: If there's enough capacity (i.e., zeros >= count_zero and ones >= count_one), recursively call 1 + calculate(strs, index + 1, zeros - count_zero, ones - count_one).
  • The function returns the maximum value obtained from these two choices.
  • The base case for the recursion is when index reaches the end of the strs array, at which point it returns 0.
  • The initial call to start the process is calculate(strs, 0, m, n).

Walkthrough

The core idea is to generate every single subset of strs. A recursive function, say calculate(strs, index, zeros, ones), is defined. This function calculates the size of the largest subset from the subarray strs[index:] given the remaining capacity of zeros and ones.

In each call, for the string at strs[index], we have two choices:

  1. Exclude strs[index]: We move to the next string without changing the zeros and ones count. The result is calculate(strs, index + 1, zeros, ones).
  2. Include strs[index]: First, we count the zeros and ones in strs[index]. If we have enough capacity (i.e., zeros >= count_zero and ones >= count_one), we include it. The result is 1 + calculate(strs, index + 1, zeros - count_zero, ones - count_one).

The function returns the maximum of the results from these two choices. The base case for the recursion is when index reaches the end of the strs array, in which case we return 0 as no more strings can be added. The initial call would be calculate(strs, 0, m, n). This method explores the entire decision tree, which has 2^L leaves, where L is the number of strings.

class Solution {    public int findMaxForm(String[] strs, int m, int n) {        return calculate(strs, 0, m, n);    }     private int calculate(String[] strs, int i, int zeros, int ones) {        if (i == strs.length) {            return 0;        }         // Calculate cost of current string        int[] count = countZerosOnes(strs[i]);        int zerosInStr = count[0];        int onesInStr = count[1];         // Option 1: Exclude strs[i]        int res = calculate(strs, i + 1, zeros, ones);         // Option 2: Include strs[i] if possible        if (zeros >= zerosInStr && ones >= onesInStr) {            res = Math.max(res, 1 + calculate(strs, i + 1, zeros - zerosInStr, ones - onesInStr));        }         return res;    }     private int[] countZerosOnes(String s) {        int[] count = new int[2];        for (char c : s.toCharArray()) {            if (c == '0') {                count[0]++;            } else {                count[1]++;            }        }        return count;    }}

Complexity

Time

O(2^L * S), where L is the length of `strs` and S is the maximum length of a string. For each of the `2^L` recursive paths, we may perform a count operation taking O(S) time. This is prohibitively slow for the given constraints.

Space

O(L), where L is the length of `strs`. This space is used by the recursion stack.

Trade-offs

Pros

  • Simple to understand and implement.

  • Follows a natural, straightforward logic.

Cons

  • Extremely inefficient due to its exponential time complexity.

  • Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.

  • Redundantly computes solutions for the same subproblems multiple times.

Solutions

class Solution { public int findMaxForm ( String [] strs , int m , int n ) { int [][] f = new int [ m + 1 ][ n + 1 ]; for ( String s : strs ) { int [] cnt = count ( s ); for ( int i = m ; i >= cnt [ 0 ]; -- i ) { for ( int j = n ; j >= cnt [ 1 ]; -- j ) { f [ i ][ j ] = Math . max ( f [ i ][ j ], f [ i - cnt [ 0 ]][ j - cnt [ 1 ]] + 1 ); } } } return f [ m ][ n ]; } private int [] count ( String s ) { int [] cnt = new int [ 2 ]; for ( int i = 0 ; i < s . length (); ++ i ) { ++ cnt [ s . charAt ( i ) - '0' ]; } return cnt ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem