Introduction

In this blog post, we will explore how to solve the LeetCode problem "916" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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 = ["lc","eo"] Output: ["leetcode"] Example 3: Input: words1 = ["acaac","cccbb","aacbb","caacc","bcbbb"], words2 = ["c","cc","b"] Output: ["cccbb"] 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.

Explanation

Here's a breakdown of the solution:

• Find the maximum frequency of each character required: Iterate through words2 and maintain a maximum frequency array (max_freq) where max_freq[i] stores the maximum frequency of the i-th alphabet across all words in words2.
• Check each word in words1: For each word in words1, check if it contains all the required characters with sufficient frequency as defined by max_freq.

• Universal Strings: If a word in words1 satisfies the condition above, it's a universal string, and add it to the result.

• Runtime Complexity: O(N + M * K), where N is the total number of characters in all strings of words1, M is the number of strings in words2, and K is the maximum length of any string in words2.

• Storage Complexity: O(1), due to the constant size of the frequency arrays (26).

Code

    def wordSubsets(words1, words2):
    def get_freq(word):
        freq = [0] * 26
        for char in word:
            freq[ord(char) - ord('a')] += 1
        return freq

    max_freq = [0] * 26
    for word in words2:
        freq = get_freq(word)
        for i in range(26):
            max_freq[i] = max(max_freq[i], freq[i])

    result = []
    for word1 in words1:
        freq1 = get_freq(word1)
        is_universal = True
        for i in range(26):
            if freq1[i] < max_freq[i]:
                is_universal = False
                break
        if is_universal:
            result.append(word1)

    return result