Word Subsets

main.md

Question

Approach

The first step was to precompute the maximum character frequencies across all the strings in words2. For example, if words2 contained the strings ["l", "e"], I determined the highest number of times each character appeared in any of these strings.

Next, for each string in the words1 list, I computed its character frequencies and compared them against the precomputed maximum frequencies from words2. If a string in words1 met or exceeded the frequency requirement for every character in the unified representation, it was deemed universal. For example, a string like "google" would pass because it contained at least one 'e' and one 'o', meeting the requirements set by words2 = ["e", "o"]. A string like "amazon" would fail because it didn’t have an 'e'.

Implmentation

class Solution:
    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
        max_freq = Counter()
        for word in words2:
            word_freq = Counter(word)
            for char, count in word_freq.items():
                max_freq[char] = max(max_freq[char], count)

        result = []
        for word in words1:
            word_freq = Counter(word)
            if all(word_freq[char] >= count for char, count in max_freq.items()):
                result.append(word)
        return result

Complexities

• Time: 𝑂 ( 𝑚 ⋅ 𝑙 2 + 𝑛 ⋅ 𝑙 1 ) where:
  • m is the size of words2 and n is the size of words1.
  • l2 is the average length of the strings in words2 and l1 is the average length of the strings in words1.
• Space: O(n).