474. Ones and Zeroes

[mah-shamim]

Topics: Array, String, Dynamic Programming

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

[mah-shamim]

We need to find the largest subset of binary strings where the total count of 0's is ≤ m and total count of 1's is ≤ n.

This is essentially a 2D knapsack problem where each string has a "weight" in terms of zeros and ones, and I need to maximize the number of items (strings) I can select without exceeding capacity m for zeros and n for ones.

Approach

I'll use dynamic programming with a 2D DP array:

• dp[i][j] = maximum number of strings that can be selected with at most i zeros and j ones
• For each string, I'll count its zeros and ones, then update the DP table

Let's implement this solution in PHP: 474. Ones and Zeroes

<?php
/**
 * @param String[] $strs
 * @param Integer $m
 * @param Integer $n
 * @return Integer
 */
function findMaxForm($strs, $m, $n) {
    // Initialize DP table
    $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));

    foreach ($strs as $str) {
        // Count zeros and ones in current string
        $zeros = substr_count($str, '0');
        $ones = strlen($str) - $zeros;

        // Update DP table from bottom-right to avoid reusing same string
        for ($i = $m; $i >= $zeros; $i--) {
            for ($j = $n; $j >= $ones; $j--) {
                $dp[$i][$j] = max($dp[$i][$j], $dp[$i - $zeros][$j - $ones] + 1);
            }
        }
    }

    return $dp[$m][$n];
}

// Test cases
// ---------- Example 1 ----------
$strs = ["10","0001","111001","1","0"];
$m = 5;
$n = 3;
echo findMaxForm($strs, $m, $n); // Output: 4

// ---------- Example 2 ----------
$strs = ["10","0","1"];
$m = 1;
$n = 1;
echo "\n" . findMaxForm($strs, $m, $n); // Output: 2
?>

Explanation:

1. DP Table Initialization: Create a 2D array dp where dp[i][j] stores the maximum strings that can be selected with i zeros and j ones.

2. String Processing: For each binary string:

   • Count zeros using substr_count($str, '0')
   • Calculate ones as string_length - zeros

3. DP Update: Update the table from bottom-right to top-left to ensure we don't reuse the same string multiple times. For each cell (i, j), we consider whether including the current string gives a better result.

4. State Transition:

   • If we don't take the string: dp[i][j] remains the same
   • If we take the string: dp[i - zeros][j - ones] + 1 (use remaining capacity + 1 string)

Complexity Analysis

• Time Complexity: O(L × m × n) where L is the number of strings
• Space Complexity: O(m × n) for the DP table

Example Walkthrough

For strs = ["10","0001","111001","1","0"], m = 5, n = 3:

• "10": zeros=1, ones=1
• "0001": zeros=3, ones=1
• "111001": zeros=2, ones=4 (exceeds n=3, so won't be selected)
• "1": zeros=0, ones=1
• "0": zeros=1, ones=0

The optimal subset is {"10", "0001", "1", "0"} with total zeros=5 and ones=3, giving answer 4.

The DP approach efficiently explores all combinations while respecting both capacity constraints.

[topugit]

Thanks for solving the problem of "Ones and Zeroes"

[mah-shamim]

Thanks