Algorithm

Problem Name: 916. Word Subsets

You are given two string arrays `words1` and `words2`.

A string `b` is a subset of string `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"`.

A string `a` from `words1` is universal if for every string `b` in `words2`, `b` is a subset of `a`.

Return an array of all the universal strings in `words1`. You may return the answer in any order.

Example 1:

```Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
```

Example 2:

```Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["l","e"]
```

Constraints:

• `1 <= words1.length, words2.length <= 104`
• `1 <= words1[i].length, words2[i].length <= 10`
• `words1[i]` and `words2[i]` consist only of lowercase English letters.
• All the strings of `words1` are unique.

Code Examples

#1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector wordSubsets(vector& A, vector& B) {
vectorres;

vectormaxCount(26);

for (int i = 0; i < B.size(); ++i) {
vector v = getCount(B[i]);

for (int j = 0; j < 26; ++j) {
maxCount[j] = max(maxCount[j], v[j]);
}
}

for (int i = 0; i < A.size(); ++i) {
vector v = getCount(A[i]);

bool isValid(true);

for (int j = 0; j < 26; ++j) {
if (v[j] < maxCount[j]) {
isValid = false;
break;
}
}

if (isValid) {
res.push_back(A[i]);
}
}

return res;
}

vector getCount(string& s) {
vectorcnt(26);

for (int i = 0; i < s.size(); ++i) {
cnt[s[i] - 'a']++;
}

return cnt;
}
};
``````
Copy The Code &

Input

cmd

Output

cmd

#2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List wordSubsets(String[] words1, String[] words2) {
int[] word2MaxCount = new int[26];
for (String word : words2) {
int[] count = getFrequencyArray(word);
for (int i = 0; i < 26; i++) {
word2MaxCount[i] = Math.max(word2MaxCount[i], count[i]);
}
}
List result = new ArrayList<>();
for (String word : words1) {
int[] count = getFrequencyArray(word);
for (int i = 0; i < 26; i++) {
if (count[i] < word2MaxCount[i]) {
break;
}
if (i == 25) {
}
}
}
return result;
}

private static int[] getFrequencyArray(String s) {
int[] count = new int[26];
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
return count;
}
}
``````
Copy The Code &

Input

cmd

Output

cmd

#3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const wordSubsets = function(A, B) {
function counter(s) {
let count = Array(26).fill(0);
for (let i = 0; i < s.length; i++) count[s.charCodeAt(i) - 97]++;
return count;
}
let aux = Array(26).fill(0);
let result = [];
for (let i = 0; i < B.length; i++) {
let count = counter(B[i]);
for (let i = 0; i < 26; i++) {
aux[i] = Math.max(aux[i], count[i]);
}
}
for (let i = 0; i < A.length; i++) {
let count = counter(A[i]);
let flag = true;
for (let j = 0; j < 26; j++) {
if (aux[j] > 0 && count[j] - aux[j] < 0) {
flag = false;
break;
}
}
if (flag) result.push(A[i]);
}
return result;
};
``````
Copy The Code &

Input

cmd

Output

cmd

#4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def wordSubsets(self, A: List[str], B: List[str]) -> List[str]:
cnt = collections.Counter()
for b in B:
for k, v in collections.Counter(b).items():
if cnt[k] < v:
cnt[k] = v
res = []
for a in A:
if not cnt - collections.Counter(a):
res.append(a)
return res
``````
Copy The Code &

Input

cmd