LeetCode 916 - Word Subsets

https://leetcode.com/problems/word-subsets/

We are given two arrays A and B of words.  Each word is a string of lowercase letters.

Now, say that word b is a subset of word a if every letter in b occurs in a, including multiplicity.  For example, "wrr" is a subset of "warrior", but is not a subset of "world".

Now say a word a from A is universal if for every b in B, b is a subset of a. 

Return a list of all universal words in A.  You can return the words in any order.

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["lo","eo"]
Output: ["google","leetcode"]

Approach 1: Reduce to Single Word in B

If b is a subset of a, then say a is a superset of b. Also, say $N_{\text{"a"}}(\text{word})$ is the count of the number of $\text{"a"}$'s in the word.

When we check whether a word wordA in A is a superset of wordB, we are individually checking the counts of letters: that for each $\text{letter}$, we have $N_{\text{letter}}(\text{wordA}) \geq N_{\text{letter}}(\text{wordB})$.

Now, if we check whether a word wordA is a superset of all words $\text{wordB}_i$, we will check for each letter and each $i$, that $N_{\text{letter}}(\text{wordA}) \geq N_{\text{letter}}(\text{wordB}_i)$. This is the same as checking $N_{\text{letter}}(\text{wordA}) \geq \max\limits_i(N_{\text{letter}}(\text{wordB}_i))$.

For example, when checking whether "warrior" is a superset of words B = ["wrr", "wa", "or"], we can combine these words in B to form a "maximum" word "arrow", that has the maximum count of every letter in each word in B.

Algorithm

Reduce B to a single word bmax as described above, then compare the counts of letters between words a in A, and bmax.

• Time Complexity: $O(\mathcal{A} + \mathcal{B})$, where $\mathcal{A}$ and $\mathcal{B}$ is the total amount of information in A and Brespectively.

    public List<String> wordSubsets(String[] A, String[] B) {
        int[] bmax = count("");
        for (String b: B) {
            int[] bCount = count(b);
            for (int i = 0; i < 26; ++i)
                bmax[i] = Math.max(bmax[i], bCount[i]);
        }

        List<String> ans = new ArrayList();
        search: for (String a: A) {
            int[] aCount = count(a);
            for (int i = 0; i < 26; ++i)
                if (aCount[i] < bmax[i])
                    continue search;
            ans.add(a);
        }

        return ans;
    }

    public int[] count(String S) {
        int[] ans = new int[26];
        for (char c: S.toCharArray())
            ans[c - 'a']++;
        return ans;
    }
https://leetcode.com/problems/word-subsets/discuss/175854/C%2B%2BJavaPython-Straight-Forward

    public List<String> wordSubsets(String[] A, String[] B) {
        int[] uni = new int[26], tmp;
        int i;
        for (String b : B) {
            tmp = counter(b);
            for (i = 0; i < 26; ++i)
                uni[i] = Math.max(uni[i], tmp[i]);
        }
        List<String> res = new ArrayList<>();
        for (String a : A) {
            tmp = counter(a);
            for (i = 0; i < 26; ++i)
                if (tmp[i] < uni[i]) break;
            if (i == 26) res.add(a);
        }
        return res;
    }

    int[] counter(String word) {
        int[] count = new int[26];
        for (char c : word.toCharArray()) count[c - 'a']++;
        return count;
    }