Ones and Zeroes - Video Solutions

Problem Overview: You get an array of binary strings and two limits: m zeros and n ones. The task is to choose the largest subset of strings such that the total number of zeros used does not exceed m and the total number of ones does not exceed n.

The constraint immediately resembles a capacity problem. Each string “costs” a certain number of zeros and ones, and the goal is to maximize how many strings you include without exceeding those limits.

Approach 1: Memoized Recursive (Top-Down DP) (Time: O(k*m*n), Space: O(k*m*n))

Treat each string as a decision point: include it or skip it. First count how many zeros and ones the current string contains. Then recursively explore two choices: skip the string and move to the next index, or include it if the remaining capacity allows. Memoization stores results for states defined by (index, remainingZeros, remainingOnes). This prevents recomputation of overlapping subproblems.

The recursion behaves exactly like a 0/1 knapsack. Each string is an item with two resource costs. Memoization ensures every state is solved once, which keeps the runtime manageable. This approach is intuitive when thinking recursively and helps visualize the decision tree.

Approach 2: Dynamic Programming (0/1 Knapsack) (Time: O(k*m*n), Space: O(m*n))

The iterative dynamic programming version compresses the state into a 2D table dp[i][j], representing the maximum number of strings you can form using i zeros and j ones. For each string, compute its zero and one counts. Then iterate the DP table backwards (from m → zeros and n → ones) to update the state.

The reverse iteration is critical. It ensures each string is used at most once, preserving the 0/1 knapsack behavior. The update rule becomes: dp[i][j] = max(dp[i][j], 1 + dp[i-zeros][j-ones]). This approach eliminates the recursion stack and reduces memory from three dimensions to two.

This problem sits at the intersection of Dynamic Programming, Array, and String processing. The key step is converting each string into resource counts, which turns the problem into a classic capacity optimization.

Recommended for interviews: The bottom-up dynamic programming solution. Interviewers expect candidates to recognize the 0/1 knapsack pattern and build a 2D DP table with reverse iteration. Discussing the recursive memoized version first shows problem decomposition skills, while implementing the iterative DP demonstrates strong dynamic programming fundamentals.