Jobs

Interviews

Discussions

Ones and Zeroes

Medium

Ones and Zeroes

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings contain characters other than '0' and '1'?
Are `m` and `n` guaranteed to be non-negative integers?
If no subset of strings can be formed within the limits of `m` and `n`, what should I return?
Can the input array of strings be empty or contain null/empty strings?
Is the goal to maximize the *number* of strings in the subset, and if so, is there a preference for using the available `m` and `n` efficiently if multiple subsets of the same size exist?

Brute Force Solution

Approach

The brute force approach to this problem involves checking absolutely every possible combination of strings to see which one maximizes the number of strings we can pick while staying within our limits for zeros and ones. It's like trying out every subset and checking if it's valid.

Here's how the algorithm would work step-by-step:

Start by considering no strings at all. This is one possibility.
Then, consider each string individually and check if using just that string exceeds our limits for zeros and ones.
Next, consider every possible pair of strings. Check if each pair exceeds our limits.
Continue this process by considering every possible group of three strings, then four, then five, and so on, checking our limits each time.
For each combination of strings that doesn't exceed our limits, keep track of the number of strings we used.
After checking every possible combination, select the combination that used the most strings. This is our best answer.

Code Implementation

def find_max_form_brute_force(strings, max_zeros, max_ones):

    maximum_strings_possible = 0

    # Iterate through all possible subsets of strings
    for i in range(1 << len(strings)):
        current_zeros = 0
        current_ones = 0
        number_of_strings = 0

        # Construct the current subset and count ones and zeros
        for j in range(len(strings)):
            # Check if j-th element is present in the subset
            if (i >> j) & 1:
                string = strings[j]
                for character in string:
                    if character == '0':
                        current_zeros += 1
                    else:
                        current_ones += 1
                number_of_strings += 1

        #Check if we can include the current subset
        if current_zeros <= max_zeros and current_ones <= max_ones:
            maximum_strings_possible = max(maximum_strings_possible, number_of_strings)

    return maximum_strings_possible

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach considers every possible subset of the input strings. Given n strings, there are 2^n possible subsets (each string can either be included or excluded). For each subset, we need to iterate through the strings in the subset to count the number of zeros and ones, and then compare these counts against the given limits. Therefore, the time complexity is dominated by the generation and processing of all possible subsets, leading to O(2^n).

Space Complexity

O(1) – The brute force approach, as described, primarily iterates through combinations of strings. It doesn't explicitly create auxiliary data structures that scale with the number of strings (N). While implicitly, some memory might be used to keep track of the current combination being tested, these variables (e.g., counters for ones and zeros) will remain constant in size regardless of the number of strings. Therefore, the auxiliary space used is constant.

Optimal Solution

Approach

The problem asks to find the largest number of strings we can form given a limited supply of zeroes and ones. The best way to solve this efficiently is to consider each string and decide whether to include it based on whether doing so leads to a better result than not including it, using a clever way to reuse past calculations.

Here's how the algorithm would work step-by-step:

Imagine you have a table that stores the best count you can achieve with a certain number of zeroes and ones, considering only the strings you've looked at so far.
Start filling this table from the ground up. Begin with having no zeroes and no ones available, and then gradually increase the available amounts.
For each string, figure out how many zeroes and ones it needs.
Now, for each cell in the table, consider two options: not using the current string or using it.
If you don't use the string, the best count is simply the value already in the cell (the best we could do with the same resources before looking at this string).
If you *do* use the string, can you afford it? If not enough zeroes or ones are available, then you can't use the string, and again the best count is what was previously there.
But if you *can* afford to use the string, then you reduce the available zeroes and ones accordingly, look up the best count with those reduced amounts from earlier in the table, add one (because you're adding this string), and compare that to the existing best count for the current number of available zeroes and ones. Choose the bigger number.
Continue filling the table this way for all possible numbers of zeroes and ones and strings. By the time you reach the end, the cell representing the total available zeroes and ones will contain the maximum number of strings you can form.
This avoids recomputing the same subproblems over and over and helps us to arrive at the optimal answer efficiently.

Code Implementation

def find_max_form(list_of_strings, max_zeroes, max_ones):
    number_of_strings = len(list_of_strings)
    # dp[i][j] is the max number of strings with i 0's and j 1's.
    dp_table = [[0] * (max_ones + 1) for _ in range(max_zeroes + 1)]

    for string in list_of_strings:
        zero_count = string.count('0')
        one_count = string.count('1')

        # Iterate backwards to avoid overwriting values needed later.
        for current_zeroes in range(max_zeroes, zero_count - 1, -1):
            for current_ones in range(max_ones, one_count - 1, -1):

                # Decide whether to include the current string.
                dp_table[current_zeroes][current_ones] = max(
                    dp_table[current_zeroes][current_ones],
                    dp_table[current_zeroes - zero_count][current_ones - one_count] + 1
                )

    # The final result is at dp[max_zeroes][max_ones].
    return dp_table[max_zeroes][max_ones]

Big(O) Analysis

Time Complexity

O(m * n * l) – The algorithm iterates through each string in the input array 'strs' of length 'l'. For each string, it iterates through a 2D table 'dp' of size (m+1) x (n+1), where 'm' is the maximum number of zeros and 'n' is the maximum number of ones. Inside the nested loops, constant time operations are performed to calculate the number of zeros and ones needed for each string and to update the 'dp' table using dynamic programming. Therefore, the time complexity is proportional to the product of these three factors, resulting in O(m * n * l).

Space Complexity

O(m * n) – The algorithm utilizes a table (dynamic programming table) to store the best count achievable with a certain number of zeroes and ones. This table has dimensions (m+1) x (n+1), where 'm' is the maximum number of zeroes allowed and 'n' is the maximum number of ones allowed. Therefore, the auxiliary space required is proportional to the product of 'm' and 'n'. No other significant data structures contribute to the space complexity.

Edge Cases

Case	How to Handle
Empty set of strings	Return 0 as no strings are available to select from, making any combinations impossible.
m or n equals zero	Return 0 as it's impossible to form any subset with zero constraints.
All strings require more 0s or 1s than m or n allow.	Return 0 because no string can be included.
Maximum values of m, n, and len(strs).	Verify dynamic programming table size remains within memory limits to avoid memory issues.
Strings with very large numbers of zeros or ones causing integer overflow when counting.	The count of zeros and ones in each string must not exceed int limits.
The set of strings contains only empty strings	The algorithm should treat empty strings as strings with zero ones and zero zeros.
Strings contain characters other than '0' or '1'	Throw an exception or filter the string if the characters are invalid to ensure accurate counting.
m and n are equal to the number of 0's and 1's in the concatenation of all the strings.	The result should be the number of strings, as including all strings satisfies the constraints.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings contain characters other than '0' and '1'?
Are `m` and `n` guaranteed to be non-negative integers?
If no subset of strings can be formed within the limits of `m` and `n`, what should I return?
Can the input array of strings be empty or contain null/empty strings?
Is the goal to maximize the *number* of strings in the subset, and if so, is there a preference for using the available `m` and `n` efficiently if multiple subsets of the same size exist?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering no strings at all. This is one possibility.
Then, consider each string individually and check if using just that string exceeds our limits for zeros and ones.
Next, consider every possible pair of strings. Check if each pair exceeds our limits.
Continue this process by considering every possible group of three strings, then four, then five, and so on, checking our limits each time.
For each combination of strings that doesn't exceed our limits, keep track of the number of strings we used.
After checking every possible combination, select the combination that used the most strings. This is our best answer.

Code Implementation

def find_max_form_brute_force(strings, max_zeros, max_ones):

    maximum_strings_possible = 0

    # Iterate through all possible subsets of strings
    for i in range(1 << len(strings)):
        current_zeros = 0
        current_ones = 0
        number_of_strings = 0

        # Construct the current subset and count ones and zeros
        for j in range(len(strings)):
            # Check if j-th element is present in the subset
            if (i >> j) & 1:
                string = strings[j]
                for character in string:
                    if character == '0':
                        current_zeros += 1
                    else:
                        current_ones += 1
                number_of_strings += 1

        #Check if we can include the current subset
        if current_zeros <= max_zeros and current_ones <= max_ones:
            maximum_strings_possible = max(maximum_strings_possible, number_of_strings)

    return maximum_strings_possible

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you have a table that stores the best count you can achieve with a certain number of zeroes and ones, considering only the strings you've looked at so far.
Start filling this table from the ground up. Begin with having no zeroes and no ones available, and then gradually increase the available amounts.
For each string, figure out how many zeroes and ones it needs.
Now, for each cell in the table, consider two options: not using the current string or using it.
If you don't use the string, the best count is simply the value already in the cell (the best we could do with the same resources before looking at this string).
If you *do* use the string, can you afford it? If not enough zeroes or ones are available, then you can't use the string, and again the best count is what was previously there.
But if you *can* afford to use the string, then you reduce the available zeroes and ones accordingly, look up the best count with those reduced amounts from earlier in the table, add one (because you're adding this string), and compare that to the existing best count for the current number of available zeroes and ones. Choose the bigger number.
Continue filling the table this way for all possible numbers of zeroes and ones and strings. By the time you reach the end, the cell representing the total available zeroes and ones will contain the maximum number of strings you can form.
This avoids recomputing the same subproblems over and over and helps us to arrive at the optimal answer efficiently.

Code Implementation

def find_max_form(list_of_strings, max_zeroes, max_ones):
    number_of_strings = len(list_of_strings)
    # dp[i][j] is the max number of strings with i 0's and j 1's.
    dp_table = [[0] * (max_ones + 1) for _ in range(max_zeroes + 1)]

    for string in list_of_strings:
        zero_count = string.count('0')
        one_count = string.count('1')

        # Iterate backwards to avoid overwriting values needed later.
        for current_zeroes in range(max_zeroes, zero_count - 1, -1):
            for current_ones in range(max_ones, one_count - 1, -1):

                # Decide whether to include the current string.
                dp_table[current_zeroes][current_ones] = max(
                    dp_table[current_zeroes][current_ones],
                    dp_table[current_zeroes - zero_count][current_ones - one_count] + 1
                )

    # The final result is at dp[max_zeroes][max_ones].
    return dp_table[max_zeroes][max_ones]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty set of strings	Return 0 as no strings are available to select from, making any combinations impossible.
m or n equals zero	Return 0 as it's impossible to form any subset with zero constraints.
All strings require more 0s or 1s than m or n allow.	Return 0 because no string can be included.
Maximum values of m, n, and len(strs).	Verify dynamic programming table size remains within memory limits to avoid memory issues.
Strings with very large numbers of zeros or ones causing integer overflow when counting.	The count of zeros and ones in each string must not exceed int limits.
The set of strings contains only empty strings	The algorithm should treat empty strings as strings with zero ones and zero zeros.
Strings contain characters other than '0' or '1'	Throw an exception or filter the string if the characters are invalid to ensure accurate counting.
m and n are equal to the number of 0's and 1's in the concatenation of all the strings.	The result should be the number of strings, as including all strings satisfies the constraints.