> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/901-1000/word-subsets.md).

# 916. Word Subsets

### Description

We are given two arrays `A` and `B` of words.  Each word is a string of lowercase letters.

Now, say that word `b` is a subset of word `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"`.

Now say a word `a` from `A` is *universal* if for every `b` in `B`, `b` is a subset of `a`. 

Return a list of all universal words in `A`.  You can return the words in any order.

### Constraints

1. `1 <= A.length, B.length <= 10000`
2. `1 <= A[i].length, B[i].length <= 10`
3. `A[i]` and `B[i]` consist only of lowercase letters.
4. All words in `A[i]` are unique: there isn't `i != j` with `A[i] == A[j]`.

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/word-subsets/)
* ProgramCreek
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** A = \["amazon", "apple", "facebook", "google", "leetcode"], B = \["e", "o"]

**Output:** \["facebook", "google", "leetcode"]
{% endtab %}

{% tab title="Example 2" %}
**Input:** A = \["amazon", "apple", "facebook", "google", "leetcode"], B = \["l", "e"]

**Output:** \["apple", "google", "leetcode"]
{% endtab %}

{% tab title="Example 3" %}
**Input:** A = \["amazon", "apple", "facebook", "google", "leetcode"], B = \["e", "oo"]

**Output:** \["facebook", "google"]
{% endtab %}

{% tab title="Example 4" %}
**Input:** A = \["amazon", "apple", "facebook", "google", "leetcode"], B = \["lo", "eo"]

**Output:** \["google", "leetcode"]
{% endtab %}

{% tab title="Example 5" %}
**Input:** A = \["amazon", "apple", "facebook", "google", "leetcode"], B = \["ec", "oc", "ceo"]

**Output:** \["facebook", "leetcode"]
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */
 
 class Solution {
    
    public List<String> wordSubsets(String[] A, String[] B) {
                
        int[] count = new int[26];
        
        for(String b: B) {
            Map<Character, Integer> map = new HashMap();
            
            for(char ch: b.toCharArray()) {
                map.put(ch, map.getOrDefault(ch, 0) + 1);
                count[ch-'a'] = Math.max(count[ch-'a'], map.get(ch));
            }
        }
        
        List<String> wordList = new ArrayList();
        
        for(String a: A) {
            Map<Character, Integer> map = new HashMap();
            for(char ch: a.toCharArray()) {
                map.put(ch, map.getOrDefault(ch, 0) + 1);
            }
            
            boolean isValid = true;
            for(char ch = 'a'; ch <= 'z'; ch++) {
                if(count[ch-'a'] > 0 && 
                    (!map.containsKey(ch) || map.get(ch) < count[ch-'a'])) {
                    isValid = false;
                    break;
                }
            }
            
            if(isValid) {
                wordList.add(a);
            }
        }
        
        return wordList;
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(A+B), where A and B is the total amount of information 
 *    in A and B respectively.
 * Space complexity : O(A.length+B.length).
 */

class Solution {
    public List<String> wordSubsets(String[] A, String[] B) {
        int[] bmax = count("");
        for (String b: B) {
            int[] bCount = count(b);
            for (int i = 0; i < 26; ++i) {
                bmax[i] = Math.max(bmax[i], bCount[i]);
            }
        }

        List<String> ans = new ArrayList();
        
        for (String a: A) {
            int[] aCount = count(a);
            boolean isValid = true;
            for (int i = 0; i < 26; ++i) {
                if (aCount[i] < bmax[i]) {
                    isValid = false;
                    break;
                }
            }
            if(isValid) {
                ans.add(a);
            }
        }

        return ans;
    }

    public int[] count(String str) {
        int[] ans = new int[26];
        for (char c: str.toCharArray())
            ans[c - 'a']++;
        return ans;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*