LeetCode 474: Ones and Zeroes Solution in Python – A Step-by-Step Guide

What Is LeetCode 474: Ones and Zeroes?

In LeetCode 474: Ones and Zeroes, you’re given an array of binary strings strs and two integers m (max zeros) and n (max ones). Your task is to find the maximum number of strings you can select from strs such that the total count of 0s is ≤ m and the total count of 1s is ≤ n. For example, with strs = ["10", "0", "1"], m = 1, n = 1, you can pick ["0", "1"] or ["10"] for a max of 2 strings. It’s like filling a binary backpack with a strict bit budget.

Problem Statement

• Input: strs (List[str])—array of binary strings; m (int)—max zeros; n (int)—max ones.
• Output: int—maximum number of strings that fit within m zeros and n ones.
• Rules:
• Each string has 0s and 1s.
• Total 0s ≤ m, total 1s ≤ n.
• Maximize number of selected strings.

Constraints

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

Examples to Get Us Started

• Input: strs = ["10","0001","111001","1","0"], m = 5, n = 6
• Output: 4 (e.g., ["10", "0001", "1", "0"]).
• Input: strs = ["10","0","1"], m = 1, n = 1
• Output: 2 (e.g., ["0", "1"]).
• Input: strs = ["10"], m = 0, n = 1
• Output: 0 (No fit).

Understanding the Problem: Packing the Bits

To solve LeetCode 474: Ones and Zeroes in Python, we need to maximize the number of strings selected from strs while keeping total 0s ≤ m and 1s ≤ n—a 2D knapsack problem where each string has a "cost" in 0s and 1s and a "value" of 1. A naive approach—trying all combinations—could be O(2^n), slow for n = 600. The key? Use dynamic programming to build a 2D table tracking max strings for each 0 and 1 limit. We’ll explore:

• Best Solution (2D Knapsack DP): O(n * m * n) time, O(m * n) space—fast and optimal.
• Alternative Solution (Brute Force Recursion): O(2^n) time, O(n) space—simple but inefficient.

Let’s dive into the DP solution—it’s the packrat’s perfect organizer we need.

Best Solution: 2D Knapsack Dynamic Programming

Why This Is the Best Solution

The 2D knapsack DP approach is the top pick because it’s O(n * m * n) time (n = len(strs), m = zeros, n = ones) and O(m * n) space, efficiently solving the problem by building a table that tracks the maximum number of strings for each combination of remaining 0s and 1s. It iterates through strings, updating the table like a classic knapsack, ensuring optimal packing. It’s like organizing a bit box with a grid, filling it step-by-step—smart and scalable!

How It Works

Here’s the strategy:

• Step 1: Create a 2D DP table dp[i][j] = max strings using i zeros and j ones.
• Step 2: For each string in strs:
• Count its 0s (zeros) and 1s (ones).
• Update dp[i][j] = max(dp[i][j], 1 + dp[i-zeros][j-ones]) if fits.
• Step 3: Iterate from top-right to bottom-left to avoid overwriting.
• Step 4: Return dp[m][n].
• Why It Works:
• DP builds incrementally, considering each string’s inclusion.
• 2D constraints (0s and 1s) fit knapsack perfectly.

Step-by-Step Example

Example: strs = ["10", "0", "1"], m = 1, n = 1

• Init: dp[2][2] = all 0s.
• "10" (1 zero, 1 one):
• dp[1][1] = max(dp[1][1], 1 + dp[0][0]) = 1.
• "0" (1 zero, 0 ones):
• dp[1][0] = 1.
• dp[1][1] = max(1, 1 + dp[0][1]) = 1 (but "10" used).
• "1" (0 zeros, 1 one):
• dp[0][1] = 1.
• dp[1][1] = max(1, 1 + dp[1][0]) = 2 ("0" + "1").
• Result: dp[1][1] = 2.

Example: strs = ["10","0001","111001","1","0"], m = 5, n = 6

• dp[6][7], process strings, final dp[5][6] = 4 (e.g., "10", "0001", "1", "0").

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        # Step 1: Initialize 2D DP table
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # Step 2: Process each string
        for s in strs:
            # Count zeros and ones
            zeros = s.count('0')
            ones = len(s) - zeros

            # Update DP table from bottom-right to top-left
            for i in range(m, zeros - 1, -1):
                for j in range(n, ones - 1, -1):
                    dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])

        # Step 3: Return max strings
        return dp[m][n]

• Line 4-5: Init dp[m+1][n+1] with zeros.
• Line 8-10: For each string, count 0s and 1s.
• Line 13-15: Update dp:
• Iterate i, j from max to min, ensuring previous values intact.
• Max of skip (dp[i][j]) or include (1 + dp[i-zeros][j-ones]).
• Line 18: Return dp[m][n].
• Time Complexity: O(n * m * n)—n strings, m*n table updates.
• Space Complexity: O(m * n)—DP table.

It’s like a binary packing pro!

Alternative Solution: Brute Force Recursion

Why an Alternative Approach?

The brute force recursion tries all combinations—O(2^n) time, O(n) space—recursively including or excluding each string without memoization. It’s slow but intuitive, like manually testing every bit pile. Good for small n or learning!

How It Works

• Step 1: Recurse with index, remaining m, n.
• Step 2: Include or skip string, track max.
• Step 3: Return max strings.

Step-by-Step Example

Example: strs = ["10","0"], m = 1, n = 1

• Index 0: "10" (m=0,n=0) → 1.
• Index 1: "0" (m=0,n=1) → 1 + 0 = 1.
• Skip: 0.
• Result: 1.

Code for Brute Force

Copy codeclass Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        def count_bits(s):
            return s.count('0'), len(s) - s.count('0')

        def recurse(index, m_left, n_left):
            if index == len(strs):
                return 0
            zeros, ones = count_bits(strs[index])
            # Skip string
            max_strings = recurse(index + 1, m_left, n_left)
            # Include string if fits
            if m_left >= zeros and n_left >= ones:
                max_strings = max(max_strings, 1 + recurse(index + 1, m_left - zeros, n_left - ones))
            return max_strings

        return recurse(0, m, n)

• Line 3-4: Count 0s and 1s.
• Line 6-14: Recurse:
• Base case: end of list, 0 strings.
• Skip or include string, take max.
• Time Complexity: O(2^n)—exponential choices.
• Space Complexity: O(n)—recursion stack.

It’s a slow bit packer!

Comparing the Two Solutions

• 2D Knapsack DP (Best):
• Pros: O(n * m * n), fast, scalable.
• Cons: O(m * n) space.
• Brute Force (Alternative):
• Pros: O(2^n), simple.
• Cons: Impractical for large n.

DP wins for efficiency.

Edge Cases and Examples

• Input: [], 5, 5 → 0.
• Input: ["0"], 0, 1 → 0.
• Input: ["1","1"], 0, 2 → 2.

DP handles all well.

Complexity Recap

• DP: Time O(n * m * n), Space O(m * n).
• Brute Force: Time O(2^n), Space O(n).

DP’s the champ.

Key Takeaways

• DP: Pack with a grid.
• Brute Force: Try all combos.
• Python Tip: DP optimizes—see [Python Basics](/python/basics).

Final Thoughts: Fill That Box

LeetCode 474: Ones and Zeroes in Python is a binary packing adventure. 2D knapsack DP is your fast organizer, while brute force is a slow stuffer. Want more knapsack fun? Try LeetCode 416: Partition Equal Subset Sum or LeetCode 322: Coin Change. Ready to pack some bits? Head to Solve LeetCode 474 on LeetCode and fill it today—your coding skills are bit-ready!