Word Subsets

Medium · Arrays & Hashing · Explanation and code example

Greedy + Hash Map

How it works

Instead of checking every word in words2 for each candidate, we can precompute a single "maximum requirement" array. The key insight is that if a word is universal, it must satisfy all words in words2 simultaneously. This means for each character, we only need the maximum count required across all words in words2. By merging all requirements into one frequency map, we reduce the problem to a single comparison per candidate word.

Steps

  1. Build a combined frequency map for words2: for each character, store the maximum count needed across all words.
  2. Iterate through each word w in words1.
  3. Count the frequency of each character in w.
  4. Compare against the combined requirement: if any character count in w is less than required, skip this word.
  5. If w meets all requirements, add it to the res list.
  6. Return the list of universal words.

Complexity

  • Time complexity: O(N * n + M * m)
  • Space complexity:
    • O(1) extra space, since we have at most 26 different characters.
    • O(N * n) space for the output list.

Where N is the size of the array words1, n is the length of the longest word in words1, M is the size of the array words2, and m is the length of the longest word in words2.

Python code example

from typing import List
from collections import Counter, defaultdict

class Solution:
    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
        count_2 = defaultdict(int)
        for w in words2:
            count_w = Counter(w)
            for c, cnt in count_w.items():
                count_2[c] = max(count_2[c], cnt)

        res = []
        for w in words1:
            count_w = Counter(w)
            flag = True
            for c, cnt in count_2.items():
                if count_w[c] < cnt:
                    flag = False
                    break
            if flag:
                res.append(w)

        return res

C++ code example

class Solution {
public:
    vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
        vector<int> count2(26, 0);
        for (string& w : words2) {
            vector<int> countW(26, 0);
            for (char c : w) countW[c - 'a']++;
            for (int i = 0; i < 26; ++i)
                count2[i] = max(count2[i], countW[i]);
        }

        vector<string> res;
        for (string& w : words1) {
            vector<int> countW(26, 0);
            for (char c : w) countW[c - 'a']++;

            bool flag = true;
            for (int i = 0; i < 26; ++i) {
                if (countW[i] < count2[i]) {
                    flag = false;
                    break;
                }
            }

            if (flag) res.push_back(w);
        }

        return res;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations