Word Subsets - Solution & Explanation

Problem Overview: You are given two string arrays words1 and words2. A word from words1 is considered universal if it contains every character required by each word in words2, including the correct frequency. The task is to return all such universal words.

Approach 1: Character Set Checking (O(n * m * k) time, O(1) space)

The direct approach compares every word in words1 with every word in words2. For each pair, build a frequency count of characters and verify whether the word from words1 contains at least the same frequency of each character required by the word in words2. If the check fails for any word in words2, the candidate word is rejected. This approach uses simple character frequency arrays (size 26 for lowercase letters) and repeated comparisons.

The drawback is redundant work. If words2 contains overlapping requirements like "e" and "ee", the same checks are repeated many times. Time complexity becomes O(n * m * k), where n is the size of words1, m is the size of words2, and k is the average word length. Space complexity stays O(1) because the alphabet size is fixed. This method relies on basic operations over string processing and character counting.

Approach 2: Frequency Map Aggregation (O(n * k + m * k) time, O(1) space)

The key insight is that every universal word must satisfy the maximum frequency requirement for each character across all words in words2. Instead of checking each requirement individually, compute a single aggregated frequency map. For every character c, store the maximum count required among all words in words2. For example, if words2 contains "e" and "ee", the requirement for e becomes 2.

Once this aggregated requirement is built, iterate through words1. For each word, compute its frequency array and verify that it meets or exceeds the required counts for all characters. If it does, add the word to the result list. This eliminates repeated checks against each word in words2.

The preprocessing step over words2 costs O(m * k). Checking all words in words1 costs O(n * k). Since the alphabet is fixed, the space complexity remains O(1). This solution heavily uses counting techniques common in hash table problems and array-based frequency tracking.

Recommended for interviews: The frequency aggregation approach is the expected solution. It shows that you can recognize repeated constraints and compress them into a single requirement. Interviewers often accept the brute-force comparison first to demonstrate understanding, but the optimized aggregation approach demonstrates stronger algorithmic reasoning and reduces unnecessary checks.