916. Word Subsets
https://leetcode.com/problems/word-subsets/description/
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"] Output: ["facebook","google","leetcode"]
Example 2:
Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["l","e"] Output: ["apple","google","leetcode"]
Constraints:
1 <= words1.length, words2.length <= 104
1 <= words1[i].length, words2[i].length <= 10
words1[i]
andwords2[i]
consist only of lowercase English letters.- All the strings of
words1
are unique.
---
Intuition
Brute force - For every word in words2 check if its a subset of word in words1
This work is repeated - words1.length * words2.length
For universal check we need to check if max character count is possible in word1
Pre compute the max freq of each character across all words in words 2
Finally check if freq of each char in word 1 covers max freq of each char in words 2
---
Time - O(M + N)
Space - O(1)
---