<commit_before>package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/ones-and-zeroes/
 */
public class Problem474 {
    public int findMaxForm(String[] strs, int m, int n) {
        ZeroOne[] array = new ZeroOne[strs.length];
        for (int i = 0; i < strs.length; i++) {
            String str = strs[i];
            int nZero = 0;
            int nOne = 0;
            for (int j = 0; j < str.length(); j++) {
                if (str.charAt(j) == '0') {
                    nZero++;
                } else {
                    nOne++;
                }
            }
            array[i] = new ZeroOne(nZero, nOne);
        }
        int max = 0;
        Map<String, Integer> memo = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            max = Math.max(max, findMaxFrom(array, m, n, i, memo));
        }
        return max;
    }

    private static int findMaxFrom(ZeroOne[] array, int m, int n, int idx, Map<String, Integer> memo) {
        if (idx == array.length) {
            return 0;
        }
        String key = idx + "|" + m + "|" + n;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        ZeroOne zeroOne = array[idx];
        if (zeroOne.nZero == m && zeroOne.nOne == n) {
            return 1;
        }
        int max = 0;
        if (zeroOne.nZero <= m & zeroOne.nOne <= n) {
            max = findMaxFrom(array, m - zeroOne.nZero, n - zeroOne.nOne, idx + 1, memo) + 1;
        } else {
            max = findMaxFrom(array, m, n, idx + 1, memo);
        }
        memo.put(key, max);
        return max;
    }

    private static class ZeroOne {
        private final int nZero;
        private final int nOne;

        public ZeroOne(int nZero, int nOne) {
            this.nZero = nZero;
            this.nOne = nOne;
        }

        @Override
        public String toString() {
            return "(0 -> " + nZero + ", 1 -> " + nOne + ")";
        }
    }

    public static void main(String[] args) {
        Problem474 prob = new Problem474();
//        System.out.println(prob.findMaxForm(new String[]{"10", "0001", "111001", "1", "0"}, 5, 3)); // 4
//        System.out.println(prob.findMaxForm(new String[]{"10", "0", "1"}, 1, 1)); // 2
//        System.out.println(prob.findMaxForm(new String[]{"10", "0", "1"}, 3, 1)); // 2
//        System.out.println(prob.findMaxForm(new String[]{"10","0001","111001","1","0"}, 3, 4)); // 3
//        System.out.println(prob.findMaxForm(new String[]{"111","1000","1000","1000"}, 9, 3)); // 3
        System.out.println(prob.findMaxForm(new String[]{"0","11","1000","01","0","101","1","1","1","0","0","0","0","1","0","0110101","0","11","01","00","01111","0011","1","1000","0","11101","1","0","10","0111"}, 9, 80)); // 17
    }
}<commit_msg>Update problem 474<commit_after>package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/ones-and-zeroes/
 */
public class Problem474 {
    public int findMaxForm(String[] strs, int m, int n) {
        ZeroOne[] array = new ZeroOne[strs.length];
        for (int i = 0; i < strs.length; i++) {
            String str = strs[i];
            int nZero = 0;
            int nOne = 0;
            for (int j = 0; j < str.length(); j++) {
                if (str.charAt(j) == '0') {
                    nZero++;
                } else {
                    nOne++;
                }
            }
            array[i] = new ZeroOne(nZero, nOne);
        }
        int max = 0;
        Map<String, Integer> memo = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            max = Math.max(max, findMaxFrom(array, m, n, i, memo));
        }
        return max;
    }

    private static int findMaxFrom(ZeroOne[] array, int m, int n, int idx, Map<String, Integer> memo) {
        if (idx == array.length) {
            return 0;
        }
        String key = idx + "|" + m + "|" + n;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        ZeroOne zeroOne = array[idx];
        if (zeroOne.nZero == m && zeroOne.nOne == n) {
            return 1;
        }
        int max = 0;
        if (zeroOne.nZero <= m & zeroOne.nOne <= n) {
            max = findMaxFrom(array, m - zeroOne.nZero, n - zeroOne.nOne, idx + 1, memo) + 1;
        } else {
            max = findMaxFrom(array, m, n, idx + 1, memo);
        }
        memo.put(key, max);
        return max;
    }

    private static class ZeroOne {
        private final int nZero;
        private final int nOne;

        public ZeroOne(int nZero, int nOne) {
            this.nZero = nZero;
            this.nOne = nOne;
        }

        @Override
        public String toString() {
            return "(0 -> " + nZero + ", 1 -> " + nOne + ")";
        }
    }

    public static void main(String[] args) {
        Problem474 prob = new Problem474();
        System.out.println(prob.findMaxForm(new String[]{"10", "0001", "111001", "1", "0"}, 5, 3)); // 4
        System.out.println(prob.findMaxForm(new String[]{"10", "0", "1"}, 1, 1)); // 2
        System.out.println(prob.findMaxForm(new String[]{"10", "0", "1"}, 3, 1)); // 2
        System.out.println(prob.findMaxForm(new String[]{"10","0001","111001","1","0"}, 3, 4)); // 3
        System.out.println(prob.findMaxForm(new String[]{"111","1000","1000","1000"}, 9, 3)); // 3
        System.out.println(prob.findMaxForm(new String[]{"0", "11", "1000", "01", "0", "101", "1", "1", "1", "0", "0", "0", "0", "1", "0", "0110101", "0", "11", "01", "00", "01111", "0011", "1", "1000", "0", "11101", "1", "0", "10", "0111"}, 9, 80)); // 17
    }
}
{'fraction_non_alphanumeric': 0.18820621468926554, 'fraction_numerical': 0.056673728813559324, 'mean_word_length': 1.8296703296703296, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 13, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2257394', 'n_tokens_mistral': 2096, 'n_tokens_neox': 1881, 'n_words': 479}