Problem of The Day: Word Subsets

Problem Statement

Brute Force [TLE]

class Solution:
    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
        res = []
        counter_arr = []
        for i, word in enumerate(words1):
            counter_arr.append([i, Counter(word)])

        for i, counter in counter_arr:
            for word in words2:
                w2_counter = Counter(word)
                isSubset = True
                for c, count in w2_counter.items():
                    if c not in counter or count > counter[c]:
                        isSubset = False
                        break
                if not isSubset:
                    break
            else:
                res.append(words1[i])

        return res

Improve Solution

class Solution:
    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
        max_freq = Counter()
        # Step 1: Calculate the maximum character requirements across all words in words2
        for word in words2:
            word_counter = Counter(word)
            for char, freq in word_counter.items():
                max_freq[char] = max(max_freq[char], freq)

        # Step 2: Check each word in words1 if it satisfies the max_freq requirements
        res = []
        for word in words1:
            word_counter = Counter(word)
            # Check if the word meets the max frequency requirement
            if all(word_counter[char] >= freq for char, freq in max_freq.items()):
                res.append(word)

        return res

Editorial

Approach 1: Reduce to Single Word in B

class Solution(object):
    def wordSubsets(self, A, B):
        def count(word):
            ans = [0] * 26
            for letter in word:
                ans[ord(letter) - ord('a')] += 1
            return ans

        bmax = [0] * 26
        for b in B:
            for i, c in enumerate(count(b)):
                bmax[i] = max(bmax[i], c)

        ans = []
        for a in A:
            if all(x >= y for x, y in zip(count(a), bmax)):
                ans.append(a)
        return ans