Word Subsets
MedPrompt
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 = ["lc","eo"]
Output: ["leetcode"]
Example 3:
Input: words1 = ["acaac","cccbb","aacbb","caacc","bcbbb"], words2 = ["c","cc","b"]
Output: ["cccbb"]
Constraints:
1 <= words1.length, words2.length <= 1041 <= words1[i].length, words2[i].length <= 10words1[i]andwords2[i]consist only of lowercase English letters.- All the strings of
words1are unique.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly translates the problem definition into code. We iterate through each word a in words1 and, for each a, we check if it is "universal". To do this, we perform another iteration through every word b in words2 and verify if b is a subset of a. If a contains all characters for every b in words2, it's added to our result list.
Algorithm
- Initialize an empty list
universalWords. - For each word
ainwords1:- Set a flag
isUniversaltotrue. - Create the character frequency map for
a, let's call itcountA. - For each word
binwords2:- Create the character frequency map for
b, let's call itcountB. - Compare the maps: if for any character
c,countB[c] > countA[c], thenbis not a subset ofa. - If
bis not a subset ofa, setisUniversaltofalseand break the inner loop.
- Create the character frequency map for
- If
isUniversalis stilltrueafter checking all words inwords2, addatouniversalWords.
- Set a flag
- Return
universalWords.
Walkthrough
The core of this method is a nested loop structure. The outer loop selects a word from words1, and the inner loop tests it against all words from words2.
A helper function can be used to determine if string b is a subset of string a. This function works by creating frequency maps (arrays of size 26 for lowercase English letters) for both strings. It then compares these maps. If the frequency of any character in b is greater than its frequency in a, b is not a subset of a.
If a word from words1 fails the subset test for any word in words2, we immediately know it's not universal and can move to the next word in words1.
import java.util.ArrayList;import java.util.List; class Solution { public List<String> wordSubsets(String[] words1, String[] words2) { List<String> result = new ArrayList<>(); for (String a : words1) { boolean isUniversal = true; for (String b : words2) { if (!isSubset(a, b)) { isUniversal = false; break; } } if (isUniversal) { result.add(a); } } return result; } private boolean isSubset(String a, String b) { int[] countA = countFreq(a); int[] countB = countFreq(b); for (int i = 0; i < 26; i++) { if (countA[i] < countB[i]) { return false; } } return true; } private int[] countFreq(String s) { int[] freq = new int[26]; for (char c : s.toCharArray()) { freq[c - 'a']++; } return freq; }}Complexity
Time
O(N * M * (L1 + L2)), where `N` is `words1.length`, `M` is `words2.length`, `L1` is the max length of a word in `words1`, and `L2` is the max length of a word in `words2`. For each of the `N * M` pairs, we build frequency maps which takes `O(L1 + L2)` time. This is too slow for the given constraints.
Space
O(L1 + L2) or O(1). Inside the loops, we create two frequency maps of size 26. Since the alphabet size is constant and the maximum word length is small, this can be considered constant auxiliary space. The space for the output list is not included.
Trade-offs
Pros
Simple to conceptualize and implement.
Directly follows the logic of the problem statement.
Cons
Highly inefficient due to the nested loops and repeated calculations of frequency maps.
Will result in a "Time Limit Exceeded" error on large test cases as specified in the problem constraints.
The key observation is that if a word a from words1 is universal, it must contain enough characters to satisfy the requirements of every word b in words2 simultaneously. This means for any character, say 'l', a must have at least as many 'l's as the word in words2 that requires the most 'l's. We can combine all the requirements from words2 into a single "master" frequency map that represents the superset of all character needs.
Algorithm
- Initialize a frequency map
maxFreqBof size 26 with all zeros. - For each word
binwords2:- Calculate the character frequency map for
b, let's call itfreqB. - For each character
cfrom 'a' to 'z':- Update
maxFreqB[c] = max(maxFreqB[c], freqB[c]).
- Update
- Calculate the character frequency map for
- Initialize an empty list
universalWords. - For each word
ainwords1:- Calculate the character frequency map for
a, let's call itfreqA. - Assume
ais universal and check iffreqAsatisfies themaxFreqBrequirements. - For each character
cfrom 'a' to 'z':- If
freqA[c] < maxFreqB[c], the word is not universal, so break the check.
- If
- If the word passed the check for all characters, add
atouniversalWords.
- Calculate the character frequency map for
- Return
universalWords.
Walkthrough
This approach avoids the nested N * M loop by pre-processing words2.
- First, we create a single frequency map, let's call it
maxFreqB, which will store the maximum frequency of each character required across all words inwords2. We iterate throughwords2, calculate the frequency map for each wordb, and updatemaxFreqBby taking the maximum count for each character. For example, ifwords2is["eo", "oo"],maxFreqBwill require one 'e' and two 'o's. - After this single pass over
words2,maxFreqBrepresents the minimum requirement for any word to be universal. - Then, we iterate through
words1just once. For each worda, we calculate its frequency map,freqA. - We compare
freqAwithmaxFreqB. IffreqA[c] >= maxFreqB[c]for all charactersc, thenais a universal word and is added to the result.
This reduces the complexity significantly.
import java.util.ArrayList;import java.util.List; class Solution { public List<String> wordSubsets(String[] words1, String[] words2) { List<String> result = new ArrayList<>(); int[] maxFreqB = new int[26]; // 1. Create a single frequency map representing the combined requirements of all words in words2. for (String b : words2) { int[] freqB = countFreq(b); for (int i = 0; i < 26; i++) { maxFreqB[i] = Math.max(maxFreqB[i], freqB[i]); } } // 2. Check each word in words1 against this single requirement map. for (String a : words1) { int[] freqA = countFreq(a); if (isUniversal(freqA, maxFreqB)) { result.add(a); } } return result; } private boolean isUniversal(int[] freqA, int[] maxFreqB) { for (int i = 0; i < 26; i++) { if (freqA[i] < maxFreqB[i]) { return false; } } return true; } private int[] countFreq(String s) { int[] freq = new int[26]; for (char c : s.toCharArray()) { freq[c - 'a']++; } return freq; }}Complexity
Time
O(N*L1 + M*L2), where `N` is `words1.length`, `M` is `words2.length`, `L1` is the max length of a word in `words1`, and `L2` is the max length of a word in `words2`. We have one pass over `words2` (`O(M*L2)`) and one pass over `words1` (`O(N*L1)`). This is very efficient and passes within the time limits.
Space
O(1) auxiliary space. We use a few fixed-size arrays (size 26) for frequency counts, which is constant space. The space for the output list is not included.
Trade-offs
Pros
Very efficient time complexity.
Avoids redundant computations by pre-calculating the total requirements from
words2.
Cons
Slightly more complex than the brute-force approach as it requires an initial insight to optimize.
Solutions
Solution
class Solution {public List<String> wordSubsets(String[] words1, String[] words2) { int[] cnt = new int[26]; for (var b : words2) { int[] t = new int[26]; for (int i = 0; i < b.length(); ++i) { t[b.charAt(i) - 'a']++; } for (int i = 0; i < 26; ++i) { cnt[i] = Math.max(cnt[i], t[i]); } } List<String> ans = new ArrayList<>(); for (var a : words1) { int[] t = new int[26]; for (int i = 0; i < a.length(); ++i) { t[a.charAt(i) - 'a']++; } boolean ok = true; for (int i = 0; i < 26; ++i) { if (cnt[i] > t[i]) { ok = false; break; } } if (ok) { ans.add(a); } } return ans; }}/** * @param {string[]} words1 * @param {string[]} words2 * @return {string[]} */ var wordSubsets = function (words1, words2) { const cnt = Array(26).fill(0); for (const b of words2) { const t = Array(26).fill(0); for (const c of b) { t[c.charCodeAt(0) - 97]++; } for (let i = 0; i < 26; i++) { cnt[i] = Math.max(cnt[i], t[i]); } } const ans = []; for (const a of words1) { const t = Array(26).fill(0); for (const c of a) { t[c.charCodeAt(0) - 97]++; } let ok = true; for (let i = 0; i < 26; i++) { if (cnt[i] > t[i]) { ok = false; break; } } if (ok) { ans.push(a); } } return ans; };class Solution {public: vector<string> wordSubsets(vector<string> &words1, vector<string> &words2) { int cnt[26] = {0}; int t[26]; for (auto &b : words2) { memset(t, 0, sizeof t); for (auto &c : b) { t[c - 'a']++; } for (int i = 0; i < 26; ++i) { cnt[i] = max(cnt[i], t[i]); } } vector<string> ans; for (auto &a : words1) { memset(t, 0, sizeof t); for (auto &c : a) { t[c - 'a']++; } bool ok = true; for (int i = 0; i < 26; ++i) { if (cnt[i] > t[i]) { ok = false; break; } } if (ok) { ans.emplace_back(a); } } return ans; }};class Solution: def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]: cnt = Counter() for b in words2: t = Counter(b) for c, v in t . items(): cnt[c] = max(cnt[c], v) ans = [] for a in words1: t = Counter(a) if all(v <= t[c] for c, v in cnt . items()): ans . append(a) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.