We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Word Subsets

Number: 952

Difficulty: Medium

Paid? No

Companies: Microsoft, Google, Amazon, Meta, Bloomberg

Problem Description

Given two arrays of strings, words1 and words2, find all strings in words1 that are universal. A string a in words1 is universal if for every string b in words2, b is a subset of a. A string b is a subset of a if every letter in b (with required multiplicity) appears in a.

Key Insights

  • Instead of checking each pair (a from words1, b from words2), precompute a combined frequency requirement.
  • For each letter, determine the maximum count needed among all strings in words2.
  • For each word in words1, simply verify if its character frequency meets or exceeds the precomputed requirements.
  • Using frequency counts minimizes unnecessary repeat computations.

Space and Time Complexity

Time Complexity: O(n1 * L + n2 * L) where n1 is the number of words1, n2 is the number of words2, and L is the average length of the words (since word lengths are small, the constants are manageable).
Space Complexity: O(1) additional space for frequency arrays of fixed size 26 plus the output list.

Solution

The solution uses frequency counting with hash (or fixed-size array of size 26 since we only have lowercase letters). First, for all words in words2, we determine the maximum frequency required for each letter. Then, for each word in words1, we count its letters and check if for every letter, its count is at least as much as the required maximum from words2. If yes, then the word is universal and added to the answer. This approach avoids checking every string in words2 for every word in words1, thus making the solution efficient.

Code Solutions

def word_subsets(words1, words2):
    # Create an array to store the maximum frequency required for each letter across words2.
    required = [0] * 26
    
    # For each word in words2, update the required frequency for each letter.
    for word in words2:
        freq = [0] * 26
        for char in word:
            freq[ord(char) - ord('a')] += 1
        for i in range(26):
            required[i] = max(required[i], freq[i])
    
    # List to store universal words from words1.
    universal_words = []
    
    # For each word in words1, check if it satisfies the required frequency.
    for word in words1:
        freq = [0] * 26
        for char in word:
            freq[ord(char) - ord('a')] += 1
        
        # Check if the word meets the requirements.
        is_universal = True
        for i in range(26):
            if freq[i] < required[i]:
                is_universal = False
                break
        if is_universal:
            universal_words.append(word)
    
    return universal_words

# Example Usage:
# words1 = ["amazon", "apple", "facebook", "google", "leetcode"]
# words2 = ["e", "o"]
# print(word_subsets(words1, words2))
← Back to All Questions