Array
String
Dynamic Programming
Description
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
Solutions
Solution 1
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12 class Solution :
def findMaxForm ( self , strs : List [ str ], m : int , n : int ) -> int :
sz = len ( strs )
f = [[[ 0 ] * ( n + 1 ) for _ in range ( m + 1 )] for _ in range ( sz + 1 )]
for i , s in enumerate ( strs , 1 ):
a , b = s . count ( "0" ), s . count ( "1" )
for j in range ( m + 1 ):
for k in range ( n + 1 ):
f [ i ][ j ][ k ] = f [ i - 1 ][ j ][ k ]
if j >= a and k >= b :
f [ i ][ j ][ k ] = max ( f [ i ][ j ][ k ], f [ i - 1 ][ j - a ][ k - b ] + 1 )
return f [ sz ][ m ][ n ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 class Solution {
public int findMaxForm ( String [] strs , int m , int n ) {
int sz = strs . length ;
int [][][] f = new int [ sz + 1 ][ m + 1 ][ n + 1 ] ;
for ( int i = 1 ; i <= sz ; ++ i ) {
int [] cnt = count ( strs [ i - 1 ] );
for ( int j = 0 ; j <= m ; ++ j ) {
for ( int k = 0 ; k <= n ; ++ k ) {
f [ i ][ j ][ k ] = f [ i - 1 ][ j ][ k ] ;
if ( j >= cnt [ 0 ] && k >= cnt [ 1 ] ) {
f [ i ][ j ][ k ] = Math . max ( f [ i ][ j ][ k ] , f [ i - 1 ][ j - cnt [ 0 ]][ k - cnt [ 1 ]] + 1 );
}
}
}
}
return f [ sz ][ m ][ n ] ;
}
private int [] count ( String s ) {
int [] cnt = new int [ 2 ] ;
for ( int i = 0 ; i < s . length (); ++ i ) {
++ cnt [ s . charAt ( i ) - '0' ] ;
}
return cnt ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 class Solution {
public :
int findMaxForm ( vector < string >& strs , int m , int n ) {
int sz = strs . size ();
int f [ sz + 1 ][ m + 1 ][ n + 1 ];
memset ( f , 0 , sizeof ( f ));
for ( int i = 1 ; i <= sz ; ++ i ) {
auto [ a , b ] = count ( strs [ i - 1 ]);
for ( int j = 0 ; j <= m ; ++ j ) {
for ( int k = 0 ; k <= n ; ++ k ) {
f [ i ][ j ][ k ] = f [ i - 1 ][ j ][ k ];
if ( j >= a && k >= b ) {
f [ i ][ j ][ k ] = max ( f [ i ][ j ][ k ], f [ i - 1 ][ j - a ][ k - b ] + 1 );
}
}
}
}
return f [ sz ][ m ][ n ];
}
pair < int , int > count ( string & s ) {
int a = count_if ( s . begin (), s . end (), []( char c ) { return c == '0' ; });
return { a , s . size () - a };
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 func findMaxForm ( strs [] string , m int , n int ) int {
sz := len ( strs )
f := make ([][][] int , sz + 1 )
for i := range f {
f [ i ] = make ([][] int , m + 1 )
for j := range f [ i ] {
f [ i ][ j ] = make ([] int , n + 1 )
}
}
for i := 1 ; i <= sz ; i ++ {
a , b := count ( strs [ i - 1 ])
for j := 0 ; j <= m ; j ++ {
for k := 0 ; k <= n ; k ++ {
f [ i ][ j ][ k ] = f [ i - 1 ][ j ][ k ]
if j >= a && k >= b {
f [ i ][ j ][ k ] = max ( f [ i ][ j ][ k ], f [ i - 1 ][ j - a ][ k - b ] + 1 )
}
}
}
}
return f [ sz ][ m ][ n ]
}
func count ( s string ) ( int , int ) {
a := strings . Count ( s , "0" )
return a , len ( s ) - a
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 function findMaxForm ( strs : string [], m : number , n : number ) : number {
const sz = strs . length ;
const f = Array . from ({ length : sz + 1 }, () =>
Array . from ({ length : m + 1 }, () => Array . from ({ length : n + 1 }, () => 0 )),
);
const count = ( s : string ) : [ number , number ] => {
let a = 0 ;
for ( const c of s ) {
a += c === '0' ? 1 : 0 ;
}
return [ a , s . length - a ];
};
for ( let i = 1 ; i <= sz ; ++ i ) {
const [ a , b ] = count ( strs [ i - 1 ]);
for ( let j = 0 ; j <= m ; ++ j ) {
for ( let k = 0 ; k <= n ; ++ k ) {
f [ i ][ j ][ k ] = f [ i - 1 ][ j ][ k ];
if ( j >= a && k >= b ) {
f [ i ][ j ][ k ] = Math . max ( f [ i ][ j ][ k ], f [ i - 1 ][ j - a ][ k - b ] + 1 );
}
}
}
}
return f [ sz ][ m ][ n ];
}
Solution 2
Python3 Java C++ Go TypeScript
class Solution :
def findMaxForm ( self , strs : List [ str ], m : int , n : int ) -> int :
f = [[ 0 ] * ( n + 1 ) for _ in range ( m + 1 )]
for s in strs :
a , b = s . count ( "0" ), s . count ( "1" )
for i in range ( m , a - 1 , - 1 ):
for j in range ( n , b - 1 , - 1 ):
f [ i ][ j ] = max ( f [ i ][ j ], f [ i - a ][ j - b ] + 1 )
return f [ m ][ n ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 class Solution {
public int findMaxForm ( String [] strs , int m , int n ) {
int [][] f = new int [ m + 1 ][ n + 1 ] ;
for ( String s : strs ) {
int [] cnt = count ( s );
for ( int i = m ; i >= cnt [ 0 ] ; -- i ) {
for ( int j = n ; j >= cnt [ 1 ] ; -- j ) {
f [ i ][ j ] = Math . max ( f [ i ][ j ] , f [ i - cnt [ 0 ]][ j - cnt [ 1 ]] + 1 );
}
}
}
return f [ m ][ n ] ;
}
private int [] count ( String s ) {
int [] cnt = new int [ 2 ] ;
for ( int i = 0 ; i < s . length (); ++ i ) {
++ cnt [ s . charAt ( i ) - '0' ] ;
}
return cnt ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Solution {
public :
int findMaxForm ( vector < string >& strs , int m , int n ) {
int f [ m + 1 ][ n + 1 ];
memset ( f , 0 , sizeof ( f ));
for ( auto & s : strs ) {
auto [ a , b ] = count ( s );
for ( int i = m ; i >= a ; -- i ) {
for ( int j = n ; j >= b ; -- j ) {
f [ i ][ j ] = max ( f [ i ][ j ], f [ i - a ][ j - b ] + 1 );
}
}
}
return f [ m ][ n ];
}
pair < int , int > count ( string & s ) {
int a = count_if ( s . begin (), s . end (), []( char c ) { return c == '0' ; });
return { a , s . size () - a };
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 func findMaxForm ( strs [] string , m int , n int ) int {
f := make ([][] int , m + 1 )
for i := range f {
f [ i ] = make ([] int , n + 1 )
}
for _ , s := range strs {
a , b := count ( s )
for j := m ; j >= a ; j -- {
for k := n ; k >= b ; k -- {
f [ j ][ k ] = max ( f [ j ][ k ], f [ j - a ][ k - b ] + 1 )
}
}
}
return f [ m ][ n ]
}
func count ( s string ) ( int , int ) {
a := strings . Count ( s , "0" )
return a , len ( s ) - a
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 function findMaxForm ( strs : string [], m : number , n : number ) : number {
const f = Array . from ({ length : m + 1 }, () => Array . from ({ length : n + 1 }, () => 0 ));
const count = ( s : string ) : [ number , number ] => {
let a = 0 ;
for ( const c of s ) {
a += c === '0' ? 1 : 0 ;
}
return [ a , s . length - a ];
};
for ( const s of strs ) {
const [ a , b ] = count ( s );
for ( let i = m ; i >= a ; -- i ) {
for ( let j = n ; j >= b ; -- j ) {
f [ i ][ j ] = Math . max ( f [ i ][ j ], f [ i - a ][ j - b ] + 1 );
}
}
}
return f [ m ][ n ];
}
GitHub