# Word Subsets
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/word-subsets)
Canonical: https://scaleengineer.com/dsa/problems/word-subsets
**Data structures:** Array, Hash Table, String
---
## Problem
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**.

# Approaches
## Brute-Force Approach
This approach directly translates the problem definition into code. We iterate through each word `a` in `words1` and, for each `a`, we check if it is "universal". To do this, we perform another iteration through every word `b` in `words2` and verify if `b` is a subset of `a`. If `a` contains all characters for every `b` in `words2`, it's added to our result list.
**Time:** O(N * M * (L1 + L2)), where `N` is `words1.length`, `M` is `words2.length`, `L1` is the max length of a word in `words1`, and `L2` is the max length of a word in `words2`. For each of the `N * M` pairs, we build frequency maps which takes `O(L1 + L2)` time. This is too slow for the given constraints. · **Space:** O(L1 + L2) or O(1). Inside the loops, we create two frequency maps of size 26. Since the alphabet size is constant and the maximum word length is small, this can be considered constant auxiliary space. The space for the output list is not included.
**Pros:** Simple to conceptualize and implement.; Directly follows the logic of the problem statement.
**Cons:** Highly inefficient due to the nested loops and repeated calculations of frequency maps.; Will result in a "Time Limit Exceeded" error on large test cases as specified in the problem constraints.
### Explanation
The core of this method is a nested loop structure. The outer loop selects a word from `words1`, and the inner loop tests it against all words from `words2`.

A helper function can be used to determine if string `b` is a subset of string `a`. This function works by creating frequency maps (arrays of size 26 for lowercase English letters) for both strings. It then compares these maps. If the frequency of any character in `b` is greater than its frequency in `a`, `b` is not a subset of `a`.

If a word from `words1` fails the subset test for any word in `words2`, we immediately know it's not universal and can move to the next word in `words1`.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> wordSubsets(String[] words1, String[] words2) {
        List<String> result = new ArrayList<>();
        for (String a : words1) {
            boolean isUniversal = true;
            for (String b : words2) {
                if (!isSubset(a, b)) {
                    isUniversal = false;
                    break;
                }
            }
            if (isUniversal) {
                result.add(a);
            }
        }
        return result;
    }

    private boolean isSubset(String a, String b) {
        int[] countA = countFreq(a);
        int[] countB = countFreq(b);
        for (int i = 0; i < 26; i++) {
            if (countA[i] < countB[i]) {
                return false;
            }
        }
        return true;
    }

    private int[] countFreq(String s) {
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }
        return freq;
    }
}
```
### Algorithm
- Initialize an empty list `universalWords`.
- For each word `a` in `words1`:
  - Set a flag `isUniversal` to `true`.
  - Create the character frequency map for `a`, let's call it `countA`.
  - For each word `b` in `words2`:
    - Create the character frequency map for `b`, let's call it `countB`.
    - Compare the maps: if for any character `c`, `countB[c] > countA[c]`, then `b` is not a subset of `a`.
    - If `b` is not a subset of `a`, set `isUniversal` to `false` and break the inner loop.
  - If `isUniversal` is still `true` after checking all words in `words2`, add `a` to `universalWords`.
- Return `universalWords`.

## Optimized Approach with Combined Requirements
The key observation is that if a word `a` from `words1` is universal, it must contain enough characters to satisfy the requirements of *every* word `b` in `words2` simultaneously. This means for any character, say 'l', `a` must have at least as many 'l's as the word in `words2` that requires the most 'l's. We can combine all the requirements from `words2` into a single "master" frequency map that represents the superset of all character needs.
**Time:** O(N*L1 + M*L2), where `N` is `words1.length`, `M` is `words2.length`, `L1` is the max length of a word in `words1`, and `L2` is the max length of a word in `words2`. We have one pass over `words2` (`O(M*L2)`) and one pass over `words1` (`O(N*L1)`). This is very efficient and passes within the time limits. · **Space:** O(1) auxiliary space. We use a few fixed-size arrays (size 26) for frequency counts, which is constant space. The space for the output list is not included.
**Pros:** Very efficient time complexity.; Avoids redundant computations by pre-calculating the total requirements from `words2`.
**Cons:** Slightly more complex than the brute-force approach as it requires an initial insight to optimize.
### Explanation
This approach avoids the nested `N * M` loop by pre-processing `words2`.

1.  First, we create a single frequency map, let's call it `maxFreqB`, which will store the maximum frequency of each character required across all words in `words2`. We iterate through `words2`, calculate the frequency map for each word `b`, and update `maxFreqB` by taking the maximum count for each character. For example, if `words2` is `["eo", "oo"]`, `maxFreqB` will require one 'e' and two 'o's.
2.  After this single pass over `words2`, `maxFreqB` represents the minimum requirement for any word to be universal.
3.  Then, we iterate through `words1` just once. For each word `a`, we calculate its frequency map, `freqA`.
4.  We compare `freqA` with `maxFreqB`. If `freqA[c] >= maxFreqB[c]` for all characters `c`, then `a` is a universal word and is added to the result.

This reduces the complexity significantly.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> wordSubsets(String[] words1, String[] words2) {
        List<String> result = new ArrayList<>();
        int[] maxFreqB = new int[26];

        // 1. Create a single frequency map representing the combined requirements of all words in words2.
        for (String b : words2) {
            int[] freqB = countFreq(b);
            for (int i = 0; i < 26; i++) {
                maxFreqB[i] = Math.max(maxFreqB[i], freqB[i]);
            }
        }

        // 2. Check each word in words1 against this single requirement map.
        for (String a : words1) {
            int[] freqA = countFreq(a);
            if (isUniversal(freqA, maxFreqB)) {
                result.add(a);
            }
        }

        return result;
    }

    private boolean isUniversal(int[] freqA, int[] maxFreqB) {
        for (int i = 0; i < 26; i++) {
            if (freqA[i] < maxFreqB[i]) {
                return false;
            }
        }
        return true;
    }

    private int[] countFreq(String s) {
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }
        return freq;
    }
}
```
### Algorithm
- Initialize a frequency map `maxFreqB` of size 26 with all zeros.
- For each word `b` in `words2`:
  - Calculate the character frequency map for `b`, let's call it `freqB`.
  - For each character `c` from 'a' to 'z':
    - Update `maxFreqB[c] = max(maxFreqB[c], freqB[c])`.
- Initialize an empty list `universalWords`.
- For each word `a` in `words1`:
  - Calculate the character frequency map for `a`, let's call it `freqA`.
  - Assume `a` is universal and check if `freqA` satisfies the `maxFreqB` requirements.
  - For each character `c` from 'a' to 'z':
    - If `freqA[c] < maxFreqB[c]`, the word is not universal, so break the check.
  - If the word passed the check for all characters, add `a` to `universalWords`.
- Return `universalWords`.

# Solutions
### Java

```java
class Solution {
public
  List<String> wordSubsets(String[] words1, String[] words2) {
    int[] cnt = new int[26];
    for (var b : words2) {
      int[] t = new int[26];
      for (int i = 0; i < b.length(); ++i) {
        t[b.charAt(i) - 'a']++;
      }
      for (int i = 0; i < 26; ++i) {
        cnt[i] = Math.max(cnt[i], t[i]);
      }
    }
    List<String> ans = new ArrayList<>();
    for (var a : words1) {
      int[] t = new int[26];
      for (int i = 0; i < a.length(); ++i) {
        t[a.charAt(i) - 'a']++;
      }
      boolean ok = true;
      for (int i = 0; i < 26; ++i) {
        if (cnt[i] > t[i]) {
          ok = false;
          break;
        }
      }
      if (ok) {
        ans.add(a);
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {string[]} words1 * @param {string[]} words2 * @return {string[]} */ var wordSubsets =
  function (words1, words2) {
    const cnt = Array(26).fill(0);
    for (const b of words2) {
      const t = Array(26).fill(0);
      for (const c of b) {
        t[c.charCodeAt(0) - 97]++;
      }
      for (let i = 0; i < 26; i++) {
        cnt[i] = Math.max(cnt[i], t[i]);
      }
    }
    const ans = [];
    for (const a of words1) {
      const t = Array(26).fill(0);
      for (const c of a) {
        t[c.charCodeAt(0) - 97]++;
      }
      let ok = true;
      for (let i = 0; i < 26; i++) {
        if (cnt[i] > t[i]) {
          ok = false;
          break;
        }
      }
      if (ok) {
        ans.push(a);
      }
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  vector<string> wordSubsets(vector<string> &words1, vector<string> &words2) {
    int cnt[26] = {0};
    int t[26];
    for (auto &b : words2) {
      memset(t, 0, sizeof t);
      for (auto &c : b) {
        t[c - 'a']++;
      }
      for (int i = 0; i < 26; ++i) {
        cnt[i] = max(cnt[i], t[i]);
      }
    }
    vector<string> ans;
    for (auto &a : words1) {
      memset(t, 0, sizeof t);
      for (auto &c : a) {
        t[c - 'a']++;
      }
      bool ok = true;
      for (int i = 0; i < 26; ++i) {
        if (cnt[i] > t[i]) {
          ok = false;
          break;
        }
      }
      if (ok) {
        ans.emplace_back(a);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]: cnt = Counter() for b in words2: t = Counter(b) for c, v in t . items(): cnt[c] = max(cnt[c], v) ans = [] for a in words1: t = Counter(a) if all(v <= t[c] for c, v in cnt . items()): ans . append(a) return ans

```