package com.fishercoder.solutions;

/**
 * 474. Ones and Zeroes
 *
 * In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.
 * For now, suppose you are a dominator of m 0s and n 1s respectively.
 * On the other hand, there is an array with strings consisting of only 0s and 1s.
 * Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s.
 * Each 0 and 1 can be used at most once.

 Note:

 The given numbers of 0s and 1s will both not exceed 100. The size of given string array won't exceed 600.

 Example 1:
 Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
 Output: 4
 Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”

 Example 2:
 Input: Array = {"10", "0", "1"}, m = 1, n = 1
 Output: 2
 Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".

 */
public class _474 {
    public static class Solution1 {
        public int findMaxForm(String[] strs, int m, int n) {
            int[][] dp = new int[m + 1][n + 1];
            for (String str : strs) {
                int[] count = count(str);
                for (int i = m; i >= count[0]; i--) {
                    for (int j = n; j >= count[1]; j--) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - count[0]][j - count[1]] + 1);
                    }
                }
            }
            return dp[m][n];
        }

        private int[] count(String str) {
            int[] res = new int[2];
            for (int i = 0; i < str.length(); i++) {
                res[str.charAt(i) - '0']++;
            }
            return res;
        }
    }

}

@@ -33,948 +33,8 @@
 s;%0A%0A
-/**%0A * 474. Ones and Zeroes%0A *%0A * In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.%0A * For now, suppose you are a dominator of m 0s and n 1s respectively.%0A * On the other hand, there is an array with strings consisting of only 0s and 1s.%0A * Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s.%0A * Each 0 and 1 can be used at most once.%0A%0A Note:%0A%0A The given numbers of 0s and 1s will both not exceed 100. The size of given string array won't exceed 600.%0A%0A Example 1:%0A Input: Array = %7B%2210%22, %220001%22, %22111001%22, %221%22, %220%22%7D, m = 5, n = 3%0A Output: 4%0A Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are %E2%80%9C10,%E2%80%9D0001%E2%80%9D,%E2%80%9D1%E2%80%9D,%E2%80%9D0%E2%80%9D%0A%0A Example 2:%0A Input: Array = %7B%2210%22, %220%22, %221%22%7D, m = 1, n = 1%0A Output: 2%0A Explanation: You could form %2210%22, but then you'd have nothing left. Better form %220%22 and %221%22.%0A%0A */%0A
 publ

refactor 474