Word Subsets

medium array hash map string

Problem

For string arrays A and B, return the words in A that are "universal" — that is, for every b in B, every letter of b appears at least as many times in a.

InputA=["amazon","apple","facebook","google"], B=["e","o"]

Output["facebook","google"]

Take the elementwise max of letter counts across B, then filter A.

A (space-separated)

B (space-separated)

from collections import Counter
def wordSubsets(A, B):
    need = [0] * 26
    for b in B:
        for ch, c in Counter(b).items():
            need[ord(ch) - 97] = max(need[ord(ch) - 97], c)
    res = []
    for a in A:
        cnt = Counter(a)
        if all(cnt[chr(97 + i)] >= need[i] for i in range(26)):
            res.append(a)
    return res

function wordSubsets(A, B) {
  const need = new Array(26).fill(0);
  for (const b of B) {
    const c = new Array(26).fill(0);
    for (const ch of b) c[ch.charCodeAt(0) - 97]++;
    for (let i = 0; i < 26; i++) need[i] = Math.max(need[i], c[i]);
  }
  const res = [];
  for (const a of A) {
    const c = new Array(26).fill(0);
    for (const ch of a) c[ch.charCodeAt(0) - 97]++;
    let ok = true;
    for (let i = 0; i < 26; i++) if (c[i] < need[i]) { ok = false; break; }
    if (ok) res.push(a);
  }
  return res;
}

class Solution {
    public List<String> wordSubsets(String[] A, String[] B) {
        int[] need = new int[26];
        for (String b : B) {
            int[] c = new int[26];
            for (char ch : b.toCharArray()) c[ch - 'a']++;
            for (int i = 0; i < 26; i++) need[i] = Math.max(need[i], c[i]);
        }
        List<String> res = new ArrayList<>();
        for (String a : A) {
            int[] c = new int[26];
            for (char ch : a.toCharArray()) c[ch - 'a']++;
            boolean ok = true;
            for (int i = 0; i < 26; i++) if (c[i] < need[i]) { ok = false; break; }
            if (ok) res.add(a);
        }
        return res;
    }
}

vector<string> wordSubsets(vector<string>& A, vector<string>& B) {
    int need[26] = {0};
    for (auto& b : B) {
        int c[26] = {0};
        for (char ch : b) c[ch - 'a']++;
        for (int i = 0; i < 26; i++) need[i] = max(need[i], c[i]);
    }
    vector<string> res;
    for (auto& a : A) {
        int c[26] = {0};
        for (char ch : a) c[ch - 'a']++;
        bool ok = true;
        for (int i = 0; i < 26; i++) if (c[i] < need[i]) { ok = false; break; }
        if (ok) res.push_back(a);
    }
    return res;
}

Explanation

A word a is "universal" only if it has enough of every letter demanded by all the words in B at once. The clever part is realizing we can collapse all of B into a single requirement before checking any word in A.

For each letter, the requirement is the maximum count that any single word in B needs. We build a 26-slot array need by taking, letter by letter, the largest count seen across B.

Why max? If one word in B needs two o's and another needs one, then a must have at least two o's to satisfy both. The bigger demand wins.

Then we just scan A. For each word we count its letters and keep it only if its count meets or beats need[i] for all 26 letters.

Example: B = ["e","o"] gives need of one e and one o. "facebook" and "google" both have an e and an o, so they pass; "amazon" has no e, so it fails.

Time: O(|A| + |B|) Space: O(1)