# Word Subsets Problem

## Description

LeetCode Problem 916.

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:

Example 2:

Example 3:

Example 4:

Example 5:

Constraints:

• 1 <= words1.length, words2.length <= 10^4
• 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.

## Sample C++ Code

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public: vector wordSubsets(vector& words1, vector& words2) { vector ans; vector universal(26, 0); for (char &ch : words2[0]) universal[ch-'a']++; for (int i = 1; i < words2.size(); ++i) { vector temp(26,0); for (char &ch : words2[i]) if (universal[ch-'a'] < ++temp[ch-'a']) universal[ch-'a']++; } for (string &str : words1) { vector freq(26, 0); for (char &ch : str) freq[ch-'a']++; bool valid = true; for (int i = 0; i < 26 && valid; i++) if (freq[i] < universal[i]) valid = false; if (valid) ans.emplace_back(str); } return ans; } };