474. Ones and Zeroes
https://leetcode.com/problems/ones-and-zeroes/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 <= 6001 <= strs[i].length <= 100strs[i]consists only of digits'0'and'1'.1 <= m, n <= 100
----
Intuition
At each position, either include the string or skip
dfs with branching factor of 2
to include make sure m, n remaining are valid
to skip, don't change m, n
memoize - 3 changing variables m, n, index
terminate recursion when no more moves are possible ie. index == length || m + n == 0
----
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int findMaxForm(String[] strs, int m, int n) { | |
| Map<String, Integer> memo = new HashMap<String, Integer>(); | |
| return dfs(strs, m, n, 0, memo); | |
| } | |
| private int[] getCount(String s) { | |
| int[] ans = new int[2]; | |
| for (char ch : s.toCharArray()) { | |
| ans[0] += ch - '0'; | |
| } | |
| ans[1] = s.length() - ans[0]; | |
| return ans; | |
| } | |
| private int dfs(String[] strs, int m, int n, int i, Map<String, Integer> memo) { | |
| // terminate when no more recursion is possible | |
| if (i == strs.length || m + n == 0) { | |
| return 0; | |
| } | |
| String key = m + "," + n + "," + i; | |
| if (memo.containsKey(key)) { | |
| return memo.get(key); | |
| } | |
| int ans = 0; | |
| int[] counts = getCount(strs[i]); | |
| // consider current string - recurse only if its a valid string | |
| if (m >= counts[1] && n >=counts[0]) { | |
| ans = 1 + dfs(strs, m - counts[1], n - counts[0], i + 1, memo); | |
| } | |
| // reject current string | |
| ans = Math.max(ans, dfs(strs, m , n , i + 1, memo)); | |
| memo.put(key, ans); | |
| return ans; | |
| } | |
| } |
