Word Subsets - Leetcode Solution

Problem Statement

We are given two arrays of strings A and B, where A[i] represents the i-th word in A and B[j] represents the j-th word in B. Now we need to return a list of all such words in A which are universal words in B. A universal word in B means that the word present in A should contain all the characters of word B[i], where B[i] is a word in B.

Example: Input: A = ["amazon","apple","facebook","google","leetcode"] B = ["e","o"] Output: ["facebook","google","leetcode"] Explanation: We can clearly see that the words "facebook", "google", and "leetcode" from array A contain all the characters of word B[0] = "e" and B[1] = "o".

Approach

To solve this problem, we can take a two-step approach.

Step 1 - Find the minimum count of each character present in every word in B We can create a count list of length 26 and initialize all the values to 0. We can then iterate through every word in B and count the frequency of every character in each word. For example, if the first word in B is "eoo", then we can increment the count of 'e' by 1 and 'o' by 2.

Once we have the frequency count of every character in every word of B, we can store the minimum count for every character. For example, if the min count of 'e' in all the words of B is 1 and the min count of 'o' in all the words of B is 2, then the minimum required count of characters 'e' and 'o' in a word of A to make it a universal word in B is 1 and 2 respectively.

Step 2 - Check whether each word in A is a universal word in B We can once again iterate through every word of A and count the frequency of every character present in it. After this, we can compare the count of each character in the word with the minimum count of each character present in all the words in B.

If the count of each character in the word is greater than or equal to the minimum count of each character in B, then we can say that the word from A is a universal word in B.

Implementation

Here's the implementation of the above approach in Python:

class Solution: def wordSubsets(self, A: List[str], B: List[str]) -> List[str]: # Initializing a count list to store the minimum count of each character present in all the words in B count = [0]*26 for word in B: freq = [0]*26 # Counting the frequency of each character present in the word for ch in word: freq[ord(ch) - ord('a')]+=1 # Updating the minimum count of each character for i in range(26): count[i] = max(count[i], freq[i])

    ans = []
    for word in A:
        freq = [0]*26
        # Counting the frequency of each character present in the word
        for ch in word:
            freq[ord(ch) - ord('a')]+=1

        isUniversal = True
        # Comparing the count of each character with the minimum count of each character in B
        for i in range(26):
            if freq[i] < count[i]:
                isUniversal = False
                break

        if isUniversal:
            ans.append(word)

    return ans

Time Complexity

For counting the frequency of each character in every word in A and B, we need to traverse every character in each word. This gives us a time complexity of O(n * k), where n is the total number of words and k is the maximum length of a word.

For finding the minimum count of each character in all the words in B, we need to traverse every character in every word in B. This gives us a time complexity of O(m * k), where m is the total number of words in B and k is the maximum length of a word.

Therefore, the overall time complexity of the solution is O((n + m) * k).

Space Complexity

We are using two count lists of length 26 to store the frequency of each character in every word in B and the minimum count of each character in B. This gives us a space complexity of O(52), which can be simplified to O(1).

The space required to store the answer list is proportional to the number of universal words in B, which can be at most n. Therefore, the overall space complexity of the solution is O(n).

1