In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.
For now, suppose you are a dominator of m 0s and n 1s respectively. On the other hand, there is an array with strings consisting of only 0s and 1s.
Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.
Note:
0s and 1s will both not exceed 100600.Example 1:
Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4
Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”
Example 2:
Input: Array = {"10", "0", "1"}, m = 1, n = 1
Output: 2
Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".
In the brute force approach we will consider every subset of array and count the total number of zeroes and ones in that subset. The subset with zeroes less than equal to and ones less than equal to will be considered as the valid subsets. The maximum length subset among all valid subsets will be our required subset.
Obviously, there are subsets possible for the list of length and here we are using int(32 bits) for iterating every subset. So this method will not work for the list having length greater than 32.
Complexity Analysis
Time complexity : . possible subsets, where is the length of the list and is the average string length.
Space complexity : . Constant Space required.
Algorithm
In the previous approach we were considering every possible subset and then we were counting its zeroes and ones. We can limit the number of subsets by breaking the loop when total number of zeroes exceed or total number of ones exceed . This will reduce little computation not the complexity.
Complexity Analysis
Time complexity : . possible subsets, where is the length of the list and is the average string length.
Space complexity : . Constant Space required.
Algorithm
In the above approaches we were considering every subset iteratively. The subset formation can also be done in a recursive manner. For this, we make use of a function calculate(strs, i, ones, zeroes). This function takes the given list of strings and gives the size of the largest subset with 1's and 0's considering the strings lying after the index(including itself) in .
Now, in every function call of calculate(...), we can:
Include the current string in the subset currently being considered. But if we include the current string, we'll need to deduct the number of 0's and 1's in the current string from the total available respective counts. Thus, we make a function call of the form . We also need to increment the total number of strings considered so far by 1. We store the result obtained from this call(including the +1) in variable.
Not include the current string in the current subset. In this case, we need not update the count of and . Thus, the new function call takes the form . The result obtained from this function call is stored in variable.
The larger value out of and represents the required result to be returned for the current function call.
Thus, the function call gives us the required maximum number of subsets possible satisfying the given constraints.
Complexity Analysis * Time complexity : . possible subsets, where is the length of the list and is the average string length.
Algorithm
In the recursive approach just discussed, a lot of redundant function calls will be made taking the same values of . This redundancy in the recursive tree can be pruned off by making use of a 3-D memoization array, .
is used to store the result obtained for the function call calculate(strs, i, j, k). Or in other words, it stores the maximum number of subsets possible considering the strings starting from the index onwards, provided only 0's and 1's are available to be used.
Thus, whenever already contains a valid entry, we need not make use of the function calls again, but we can pick up the result directly from the array.
The rest of the procedure remains the same as that of the recursive approach.
Complexity Analysis
Time complexity : . array of size is filled, where is the length of , and are the number of zeroes and ones respectively.
Space complexity : . 3D array is used.
Algorithm
This problem can be solved by using 2-D Dynamic Programming. We can make use of a array, such that an entry denotes the maximum number of strings that can be included in the subset given only 0's and 1's are available.
Now, let's look at the process by which we'll fill the array. We traverse the given list of strings one by one. Suppose, at some point, we pick up any string consisting of zeroes and ones. Now, choosing to put this string in any of the subset possible by using the previous strings traversed so far will impact the element denoted by for and satisfying , . This is because for entries with or , there won't be sufficient number of 1's and 0's available to accomodate the current string in any subset.
Thus, for every string encountered, we need to appropriately update the entries within the correct range.
Further, while updating the values, if we consider choosing the current string to be a part of the subset, the updated result will depend on whether it is profitable to include the current string in any subset or not. If included in the subset, the entry needs to be updated as , where the factor of +1 takes into account the number of elements in the current subset being increased due to a new entry.
But, it could be possible that the current string could be so long that it could be profitable not to include it in any of the subsets. Thus, the correct equation for updation becomes:
Thus, after the complete list of strings has been traversed, gives the required size of the largest subset.
Watch this animation for clear understanding:
!?!../Documents/474_Ones_Zeroes.json:1000,563!?!
Complexity Analysis
Time complexity : . Three nested loops are their, where is the length of , and are the number of zeroes and ones respectively.
Space complexity : . array of size is used.
Analysis written by: @vinod23