Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
474. Ones and Zeroes
Bookmark
Recursion
Memoization
Dynamic Programming
Input
LeetCode Example 1
Small
Medium
Tight budget
Custom
strs
=
[10, 0001, 111001, 1, 0]
,
m
=
5
,
n
=
3
strs
10
0001
111001
1
0
m =
5
n =
3
ones budget j
0
1
2
3
zeros budget i
0
1
2
3
4
5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
pick the most strings that fit the budget: 5 zeros and 3 ones
strs
10
0001
111001
1
0
m =
5
n =
3
ones budget j
0
1
2
3
zeros budget i
0
1
2
3
4
5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
pick the most strings that fit the budget: 5 zeros and 3 ones
strs
1
0
0001
111001
1
0
m =
5
n =
3
cost
1
/
1
s
ones budget j
0
1
2
3
zeros budget i
0
1
2
3
4
5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
1
1
1
+1
dp[4][1]
=
0
+ 1 =
1
take
"10"
strs
1
0
0001
111001
1
0
m =
5
n =
3
cost
1
/
1
s
ones budget j
0
1
2
3
zeros budget i
0
1
2
3
4
5
0
0
0
0
0
0
0
1
0
1
1
1
0
1
1
1
0
1
1
1
0
1
1
1
+1
dp[1][2]
= max(
0
, dp[
0
][
1
] + 1 =
1
)
strs
10
0
0
0
1
111001
1
0
m =
5
n =
3
cost
3
/
1
s
ones budget j
0
1
2
3
zeros budget i
0
1
2
3
4
5
0
0
0
0
0
1
1
1
0
1
1
1
0
1
1
1
0
1
2
2
0
1
2
2
+1
dp[4][2]
=
1
+ 1 =
2
take
"0001"
strs
10
0001
111001
1
0
m =
5
n =
3
cost
0
/
1
s
ones budget j
0
1
2
3
zeros budget i
0
1
2
3
4
5
0
0
0
0
0
1
1
1
0
1
1
1
0
1
1
1
0
1
2
2
0
1
2
3
+1
dp[5][2]
= max(
2
, dp[
5
][
1
] + 1 =
2
)
strs
10
0001
111001
1
0
m =
5
n =
3
cost
0
/
1
s
ones budget j
0
1
2
3
zeros budget i
0
1
2
3
4
5
0
0
0
0
0
1
1
1
0
1
1
1
0
1
2
2
0
1
2
3
0
1
2
3
+1
dp[2][3]
= max(
1
, dp[
2
][
2
] + 1 =
2
)
strs
10
0001
111001
1
0
m =
5
n =
3
cost
0
/
1
s
ones budget j
0
1
2
3
zeros budget i
0
1
2
3
4
5
0
0
1
1
0
1
2
2
0
1
2
2
0
1
2
2
0
1
2
3
0
1
2
3
+1
dp[0][2]
=
0
+ 1 =
1
take
"1"
strs
10
0001
111001
1
0
m =
5
n =
3
cost
1
/
0
s
ones budget j
0
1
2
3
zeros budget i
0
1
2
3
4
5
0
1
1
1
0
1
2
2
0
1
2
2
0
1
2
2
0
1
2
3
1
2
3
4
+1
dp[4][2]
= max(
2
, dp[
3
][
2
] + 1 =
3
)
strs
10
0001
111001
1
0
m =
5
n =
3
cost
1
/
0
s
ones budget j
0
1
2
3
zeros budget i
0
1
2
3
4
5
0
1
1
1
0
1
2
2
0
1
2
3
1
2
3
3
1
2
3
3
1
2
3
4
+1
dp[2][3]
=
2
+ 1 =
3
take
"0"
strs
10
0001
111001
1
0
m =
5
n =
3
ones budget j
0
1
2
3
zeros budget i
0
1
2
3
4
5
0
1
1
1
1
2
2
2
1
2
3
3
1
2
3
3
1
2
3
3
1
2
3
4
max subset = dp[5][3] =
4 strings
algo
master
.
io
Step:
Pick as many strings as possible using at most 5 zeros and 3 ones
0 / 136
Input
LeetCode Example 1
Small
Medium
Tight budget
Custom
strs
=
[10, 0001, 111001, 1, 0]
,
m
=
5
,
n
=
3
0 / 136
algo
master
.
io
Step:
Pick as many strings as possible using at most 5 zeros and 3 ones
