916. Word Subsets

[mah-shamim]

Topics: Array, Hash Table, String

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.

• For example, "wrr" is a subset of "warrior" but is not a subset of "world".

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.

Example 1:

• Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
• Output: ["facebook","google","leetcode"]

Example 2:

• Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["l","e"]
• Output: ["apple","google","leetcode"]

Constraints:

• 1 <= words1.length, words2.length <= 104
• 1 <= words1[i].length, words2[i].length <= 10
• words1[i] and words2[i] consist only of lowercase English letters.
• All the strings of words1 are unique.

[mah-shamim]

We need to identify the words in words1 that are "universal", meaning each string in words2 is a subset of the word from words1.

Approach:

1. Count the Frequency of Characters in words2:

   • First, we need to determine the maximum count for each character across all strings in words2. This gives us the required number of occurrences for each character to be a subset.

2. Check Each Word in words1:

   • For each word in words1, count the frequency of each character.
   • If the character counts in the word from words1 meet or exceed the required counts from words2, then the word is universal.

3. Return the Universal Words:

   • After checking all words in words1, return the ones that are universal.

Let's implement this solution in PHP: 916. Word Subsets

<?php
/**
 * @param String[] $words1
 * @param String[] $words2
 * @return String[]
 */
function wordSubsets($words1, $words2) {
    // Step 1: Build a frequency map for the maximum counts of characters in words2
    $freqB = [];
    foreach ($words2 as $word) {
        $count = count_chars($word, 1); // get character counts for each word in words2
        foreach ($count as $char => $c) {
            $freqB[$char] = max(isset($freqB[$char]) ? $freqB[$char] : 0, $c);
        }
    }

    // Step 2: Check each word in words1
    $result = [];
    foreach ($words1 as $word) {
        $countA = count_chars($word, 1); // get character counts for the word in words1
        $isValid = true;

        // Step 3: Check if the word in words1 meets the required character frequencies
        foreach ($freqB as $char => $freq) {
            if (isset($countA[$char]) && $countA[$char] >= $freq) {
                continue;
            }
            $isValid = false;
            break;
        }

        // Step 4: If valid, add the word to the result
        if ($isValid) {
            $result[] = $word;
        }
    }

    return $result;
}

// Example usage:
$words1 = ["amazon", "apple", "facebook", "google", "leetcode"];
$words2 = ["e", "o"];
print_r(wordSubsets($words1, $words2));  // Output: ["facebook", "google", "leetcode"]

$words2 = ["l", "e"];
print_r(wordSubsets($words1, $words2));  // Output: ["apple", "google", "leetcode"]
?>

Explanation:

1. Building Frequency Map for words2: We loop through each word in words2 and calculate the frequency of each character. We keep track of the maximum frequency needed for each character across all words in words2.

2. Checking words1 Words: For each word in words1, we calculate the frequency of each character and compare it with the required frequency from words2. If the word meets the requirements for all characters, it's considered universal.

3. Result: We store all the universal words in the result array and return it at the end.

Time Complexity:

• Building the frequency map for words2: O(n * m), where n is the length of words2 and m is the average length of words in words2.
• Checking words1: O(k * m), where k is the length of words1 and m is the average length of words in words1.
• The total time complexity is approximately O(n * m + k * m).

This approach ensures that we check each word efficiently and meets the problem's constraints.

[basharul-siddike]

Thanks to solving the problem of "Word Subsets"

[mah-shamim]

Thanks