916. Word Subsets

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:

---

Intuition

Brute force - For every word in words2 check if its a subset of word in words1

This work is repeated - words1.length * words2.length

For universal check we need to check if max character count is possible in word1

Pre compute the max freq of each character across all words in words 2

Finally check if freq of each char in word 1 covers max freq of each char in words 2

---

Time - O(M + N)

Space - O(1)

---

	class Solution {
	public List<String> wordSubsets(String[] words1, String[] words2) {
	List<String> ans = new ArrayList<String>();
	if (words1 == null \|\| words2 == null \|\| words1.length == 0\|\| words2.length == 0) {
	return ans;
	}

	int[] count = new int[26];

	for (String w: words2) {
	int[] temp = count(w);
	for (int i = 0; i < count.length; i++) {
	count[i] = Math.max(count[i], temp[i]);
	}
	}

	for (String w: words1) {
	int[] temp = count(w);

	for (int i = 0; i < count.length; i++) {
	if (temp[i] < count[i]) {
	break;
	}
	if (i == 25) {
	ans.add(w);
	}
	}
	}

	return ans;
	}

	private int[] count(String s) {
	int[] ans = new int[26];

	for (int i = 0; i < s.length(); i++) {
	int index = s.charAt(i) - 'a';
	ans[index]++;
	}
	return ans;
	}
	}

SWE Interview preparation