Word Subsets

Word Subsets

What is this problem about?

You are given two arrays of strings, A and B. A string from A is "universal" if every string in B is a subset of it. A string b is a subset of a if every letter in b appears in a, including repeats (e.g., if b has two 'o's, a must have at least two 'o's). You need to return all universal strings in A.

Why is this asked in interviews?

This problem tests your ability to simplify constraints. Comparing every string in A with every string in B is O(A * B). Interviewers at Microsoft and Meta want to see if you can "compress" the requirements of B into a single character count array. This evaluates your skill in Hash Tables and Frequency Counting.

Algorithmic pattern used

The pattern is Character Frequency Counting.

1. For all strings in B, find the maximum frequency of each character required. For example, if B = ["eo", "oo"], the requirement is one 'e' and two 'o's.
2. Store this in a maxFreqB array of size 26.
3. For each string in A, count its characters and check if they satisfy the maxFreqB requirements.

Example explanation

A: ["amazon", "apple", "facebook", "google"], B: ["e", "o"].

1. Requirement from B: 'e' >= 1, 'o' >= 1.
2. amazon: 'a': 2, 'm': 1, 'z': 1, 'o': 1, 'n': 1. Missing 'e'. NO.
3. apple: Missing 'o'. NO.
4. facebook: 'f': 1, 'a': 1, 'c': 1, 'e': 1, 'b': 1, 'o': 2, 'k': 1. Has 'e' and 'o'. YES.
5. google: 'g': 2, 'o': 2, 'l': 1, 'e': 1. Has 'e' and 'o'. YES. Result: ["facebook", "google"].

Common mistakes candidates make

• Repeating work: Re-checking every string in B for every string in A.
• Handling duplicates incorrectly: Not realizing that "subset" means the character count must be greater than or equal to the maximum count of that character across any single word in B.
• Inefficient comparisons: Not using a fixed-size array (26 chars) for counts.

Interview preparation tip

When a problem asks you to compare one set of items against another based on "components" (like letters), look for a way to aggregate the second set into a single "representative" object.