Is Word Subsets easy or hard?

Word Subsets is classified as a Medium problem. The main challenge is recognizing that requirements from words2 can be merged into a single maximum frequency constraint instead of checking each word individually.

How to solve Word Subsets in O(n)?

Strict O(n) is not possible because each word must be scanned character by character. The closest optimal approach is O(n * k + m * k), which uses a precomputed maximum frequency requirement from words2 and then checks each word in words1 against it.

What is the best approach for Word Subsets?

The frequency map aggregation approach is the most efficient solution. It first computes the maximum required frequency of each character across all words in words2, then checks each word in words1 against this combined requirement. This removes repeated comparisons and reduces the time complexity to O(n * k + m * k).

What data structure is used in Word Subsets?

The solution primarily uses a fixed-size frequency array or hash map to store character counts. Because the problem uses lowercase English letters, a 26-length array is typically used for efficient counting and comparison.

What is the time complexity of Word Subsets?

The optimal solution runs in O(n * k + m * k) time, where n is the number of words in words1, m is the number of words in words2, and k is the average word length. Each word is processed once to build or compare character frequencies.

Word Subsets Python or Java solution approach?

Both Python and Java implementations follow the same strategy: build a maximum frequency requirement from words2, then compute the frequency of each word in words1 and compare it against that requirement. The logic is identical across languages.

Is Word Subsets asked at Google, Amazon, or Meta?

Word Subsets is a common medium-level string and hash table problem frequently used in coding interview preparation. Variations of character frequency aggregation and constraint merging appear in interviews at companies like Amazon, Google, and Meta.

Description Solution Video 8:39

916. Word Subsets

Medium55.9% acceptance6 companies

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 <= 10⁴
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.

Asked at 6 companies

Zoho

Google Amazon Microsoft Meta Bloomberg

Topics

8:39

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

["amazon","apple","facebook","google","leetcode"]
["e","o"]

Input

["amazon","apple","facebook","google","leetcode"]
["lc","eo"]

Input

["acaac","cccbb","aacbb","caacc","bcbbb"]
["c","cc","b"]

Your code is saved on this device.Solution