474. Ones and Zeroes¶
Edited by Charles
Medium · Python · Dynamic Programming
Problem
Read the original problem on LeetCode.
The official page contains the problem statement, examples, and constraints.
Explanation, examples & other approaches
Core idea
dp[i][j]: the size of the largest subset with at most number i of 0s and number j of 1s. dp[i][j] = max(dp[i][j], dp[i - numZero][j - numOne] + 1), where numZero and numOne are nubmers of 0s and 1s in the last iterated string (for s in strs).
Original study notes follow, including intermediate snippets and earlier attempts.
Note:
- dp[i][j]: the size of the largest subset with at most number i of 0s and number j of 1s.
- dp[i][j] = max(dp[i][j], dp[i - numZero][j - numOne] + 1), where numZero and numOne are nubmers of 0s and 1s in the last iterated string (for s in strs).
Study record
| Field | Value |
|---|---|
| Attempts | 1 |
| Mastery | ❚ |
| The Latest Attempt | February 5, 2026 |
Python solution¶
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
dp = [[0] * (n + 1) for _ in range(m + 1)]
for s in strs:
zeroNum = s.count('0')
oneNum = len(s) - zeroNum
for i in range(m, zeroNum - 1, -1):
for j in range(n, oneNum - 1, -1):
dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)
return dp[-1][-1]