Skip to main content

916 - Word Subsets

Difficulty: Medium | Pattern: HashMap / Counter | Company tags: Google, Amazon

Problem Statement​

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 not of "world".

A string a from words1 is universal if for every 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:

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

Approach: Max Frequency Counter — O(n × L)​

Key insight: A word in words1 is universal if it contains every word in words2 as a subset. Merge all words2 requirements into a single max-frequency counter: for each character, take the max frequency needed across all words in words2.

from collections import Counter

def wordSubsets(words1: list[str], words2: list[str]) -> list[str]:
    # Build max requirement
    max_req = Counter()
    for b in words2:
        for c, cnt in Counter(b).items():
            max_req[c] = max(max_req[c], cnt)
    
    result = []
    for a in words1:
        cnt_a = Counter(a)
        if all(cnt_a[c] >= req for c, req in max_req.items()):
            result.append(a)
    
    return result

Dry Run​

words2 = ["ec","oc","ceo"]

Per word: (e:1,c:1), (o:1,c:1), (c:1,e:1,o:1)

max_req: e→1, c→1, o→1

Check "facebook": Counter has f,a,c,e,b,o,o,k → c=1,e=1,o=2 → all satisfy max_req ✓

Why Max Frequency Works?​

If a word satisfies the max requirement, it satisfies every individual word2's requirement (since each word2 requires at most as much as the max).

Complexity​

  • Time: O(A + B) where A and B are total chars in words1 and words2
  • Space: O(1) — counters bounded by 26 chars