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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Word Subsets

Difficulty: Medium

Problem Description

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

Key Insights

  • A string is a subset of another if all characters exist in the second string with at least the same frequency.
  • We can determine the maximum frequency of each character required from words2.
  • Each string in words1 must be checked against this frequency to determine if it is universal.

Space and Time Complexity

Time Complexity: O(n * m + k), where n is the length of words1, m is the maximum length of a string in words2, and k is the number of unique characters. Space Complexity: O(1), since the frequency count is fixed at 26 for lowercase letters.

Solution

To solve this problem, we will:

  1. Create a frequency count of characters needed based on all strings in words2.
  2. For each string in words1, check if it meets the required frequency of characters.
  3. Return all strings from words1 that are universal.

We will use an array of size 26 (for each letter) to count the characters, as the input consists only of lowercase English letters.

Code Solutions

def wordSubsets(words1, words2):
    from collections import Counter
    
    # Step 1: Create a frequency count for words2
    max_count = Counter()
    for word in words2:
        count = Counter(word)
        for char, freq in count.items():
            max_count[char] = max(max_count[char], freq)

    # Step 2: Check each word in words1
    result = []
    for word in words1:
        count = Counter(word)
        if all(count[char] >= freq for char, freq in max_count.items()):
            result.append(word)
    
    return result
← Back to All Questions