Problem Description

You are given two arrays of strings: words1 and words2.

A string b is considered a subset of string a if every letter in b appears in a with at least the same frequency. In other words, a must contain all letters from b, and each letter must appear at least as many times as it does in b.

For example:

• "wrr" is a subset of "warrior" because "warrior" contains at least one 'w' and at least two 'r's
• "wrr" is NOT a subset of "world" because "world" only has one 'r' while "wrr" needs two

A string a from words1 is called universal if every single string b in words2 is a subset of a. This means a must satisfy the subset requirement for all strings in words2 simultaneously.

Your task is to find all universal strings from words1 and return them in an array. The order of strings in the result doesn't matter.

The solution works by first finding the maximum frequency requirement for each character across all strings in words2. This creates a "combined requirement" stored in cnt. Then, for each string in words1, it checks if that string meets all the character frequency requirements. If a string from words1 contains enough of each required character, it's added to the answer list.

Intuition

The key insight is recognizing that we need to find strings in words1 that can satisfy all strings in words2 simultaneously.

Think about what it means for a string a to be universal - it must be a superset of every string in words2. If we have words2 = ["ec", "oc", "ceo"], then a must contain:

• At least 1 'e' and 1 'c' (to satisfy "ec")
• At least 1 'o' and 1 'c' (to satisfy "oc")
• At least 1 'c', 1 'e', and 1 'o' (to satisfy "ceo")

Notice that we need to satisfy all these requirements at once. So for character 'c', we need at least 1 occurrence (the maximum required across all strings in words2). For 'e', we need at least 1, and for 'o', we need at least 1.

This leads us to the realization: instead of checking each string in words1 against every string in words2 (which would be inefficient), we can merge all requirements from words2 into a single "combined requirement".

For each character, we take the maximum frequency required across all strings in words2. Why maximum? Because if a character appears 2 times in one word and 3 times in another word from words2, we need at least 3 occurrences to satisfy both requirements.

Once we have this combined requirement (stored in cnt), checking becomes simple: for each string in words1, we just need to verify it meets or exceeds the frequency requirement for each character in our combined requirement. This transforms a complex multiple-comparison problem into a single comparison problem.

Solution Approach

The solution uses a counting approach with hash maps (Python's Counter) to efficiently track character frequencies.

Step 1: Build the Combined Requirement

First, we create an empty counter cnt to store the maximum frequency requirement for each character across all strings in words2.

cnt = Counter()
for b in words2:
    t = Counter(b)
    for c, v in t.items():
        cnt[c] = max(cnt[c], v)

For each string b in words2:

• Count the frequency of each character using Counter(b) and store it in t
• For each character c with frequency v in the current string, update cnt[c] to be the maximum of its current value and v

For example, if words2 = ["ec", "oc", "ceo"]:

• After processing "ec": cnt = {'e': 1, 'c': 1}
• After processing "oc": cnt = {'e': 1, 'c': 1, 'o': 1}
• After processing "ceo": cnt = {'e': 1, 'c': 1, 'o': 1} (no changes as frequencies don't exceed existing maximums)

Step 2: Check Each String in words1

Now we iterate through each string a in words1 and check if it satisfies the combined requirement:

ans = []
for a in words1:
    t = Counter(a)
    if all(v <= t[c] for c, v in cnt.items()):
        ans.append(a)

For each string a:

• Count its character frequencies using Counter(a) and store in t
• Check if for every character c with required frequency v in cnt, the string a has at least v occurrences of that character (v <= t[c])
• If all requirements are satisfied, add a to the answer list

The all() function returns True only if every character requirement is met. If any character appears fewer times in a than required by cnt, the string is not universal.

Time Complexity: O(M + N) where M is the total number of characters across all strings in words2 and N is the total number of characters across all strings in words1.

Space Complexity: O(1) for the character counters since there are at most 26 lowercase English letters.

Example Walkthrough

Let's walk through a concrete example with words1 = ["amazon", "apple", "facebook", "google", "leetcode"] and words2 = ["e", "o"].

Step 1: Build the Combined Requirement

We need to find the maximum frequency requirement for each character across all strings in words2:

• Process "e":

  • Character frequencies: {'e': 1}
  • Update cnt: cnt = {'e': 1}

• Process "o":

  • Character frequencies: {'o': 1}
  • Update cnt: cnt = {'e': 1, 'o': 1}

So our combined requirement is: any universal string must have at least 1 'e' and at least 1 'o'.

Step 2: Check Each String in words1

Now we check each string in words1 against this combined requirement:

1. "amazon":

   • Character frequencies: {'a': 2, 'm': 1, 'z': 1, 'o': 1, 'n': 1}
   • Check: needs 'e' ≥ 1 (has 0) ❌
   • Not universal

2. "apple":

   • Character frequencies: {'a': 1, 'p': 2, 'l': 1, 'e': 1}
   • Check: needs 'e' ≥ 1 (has 1) ✓, needs 'o' ≥ 1 (has 0) ❌
   • Not universal

3. "facebook":

   • Character frequencies: {'f': 1, 'a': 1, 'c': 1, 'e': 1, 'b': 1, 'o': 2, 'k': 1}
   • Check: needs 'e' ≥ 1 (has 1) ✓, needs 'o' ≥ 1 (has 2) ✓
   • Universal! Add to answer

4. "google":

   • Character frequencies: {'g': 2, 'o': 2, 'l': 1, 'e': 1}
   • Check: needs 'e' ≥ 1 (has 1) ✓, needs 'o' ≥ 1 (has 2) ✓
   • Universal! Add to answer

5. "leetcode":

   • Character frequencies: {'l': 1, 'e': 3, 't': 1, 'c': 1, 'o': 1, 'd': 1}
   • Check: needs 'e' ≥ 1 (has 3) ✓, needs 'o' ≥ 1 (has 1) ✓
   • Universal! Add to answer

Final Answer: ["facebook", "google", "leetcode"]

These three strings are universal because they each contain at least one 'e' and at least one 'o', satisfying all strings in words2.

Solution Implementation

Time and Space Complexity

Time Complexity: O(L), where L is the sum of the lengths of all words in words1 and words2.

• Building the maximum frequency counter for words2: We iterate through each word in words2 and count the frequency of each character. For each word b in words2, creating Counter(b) takes O(len(b)) time. Updating the maximum frequencies takes O(26) at most (for lowercase English letters). The total time for processing words2 is O(sum of lengths of words in words2).

• Checking each word in words1: For each word a in words1, creating Counter(a) takes O(len(a)) time. The all() check iterates through at most 26 unique characters in cnt, each lookup in t is O(1). The total time for processing words1 is O(sum of lengths of words in words1).

• Overall: O(sum of lengths in words1 + sum of lengths in words2) = O(L)

Space Complexity: O(1) or O(26) for the character space, which is constant.

• The cnt counter stores at most 26 lowercase English letters with their maximum frequencies: O(26) = O(1)
• For each word being processed, the temporary counter t also stores at most 26 characters: O(26) = O(1)
• The output list ans stores references to strings from words1, not creating new strings: O(|words1|) in the worst case when all words are universal

If we consider the output space, the space complexity is O(|words1|). If we only consider auxiliary space excluding the output, it's O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Checking Against Individual Words Instead of Combined Requirements

The Mistake: A common error is to check if each word in words1 is a superset of each word in words2 individually, like this:

# INCORRECT APPROACH
result = []
for a in words1:
    is_universal = True
    for b in words2:
        if not is_subset(b, a):  # Check each b individually
            is_universal = False
            break
    if is_universal:
        result.append(a)

Why It's Wrong: While this seems logical, it's inefficient and leads to redundant checks. If words2 = ["a", "aa", "aaa"], you'd check the same character 'a' multiple times for each word in words1.

The Fix: Pre-compute the maximum frequency requirement for each character across ALL words in words2 first, then check each word in words1 against this combined requirement only once.

Pitfall 2: Using Set Operations Instead of Frequency Counting

The Mistake:

# INCORRECT - only checks presence, not frequency
max_chars = set()
for word in words2:
    max_chars.update(word)

result = []
for word in words1:
    if max_chars.issubset(set(word)):
        result.append(word)

Why It's Wrong: Sets only track whether a character exists, not how many times it appears. The word "world" would incorrectly be considered universal for words2 = ["wrr"] because both contain 'w' and 'r', ignoring that "wrr" needs TWO 'r's.

The Fix: Use Counter or frequency maps to track the exact count of each character, not just its presence.

Pitfall 3: Incorrectly Accumulating Character Frequencies

The Mistake:

# INCORRECT - sums frequencies instead of taking maximum
cnt = Counter()
for b in words2:
    cnt += Counter(b)  # Wrong: adds frequencies together

Why It's Wrong: If words2 = ["aa", "aaa"], this would require 5 'a's (2+3) in each universal string. But the actual requirement is only 3 'a's (the maximum from any single word).

The Fix: Use max() to keep only the highest frequency requirement for each character:

for b in words2:
    t = Counter(b)
    for c, v in t.items():
        cnt[c] = max(cnt[c], v)

Pitfall 4: Missing Edge Case - Empty Character Count

The Mistake:

# Potential KeyError if character doesn't exist in word from words1
if all(v <= t[c] for c, v in cnt.items()):  # t[c] might not exist

Why It's Wrong: If a required character doesn't exist in the word from words1, accessing t[c] could cause issues in some implementations.

The Fix: Python's Counter handles this gracefully by returning 0 for missing keys, but in other languages or data structures, you might need:

if all(v <= t.get(c, 0) for c, v in cnt.items()):