Word Subsets — Editorial

Opening the reading…

Intuitionwhy many subset checks become one frequency check

A word b is a subset of a when a contains every letter of b with enough copies. If words2 contains e and eo, a universal word must contain at least one e and at least one o; the two requirements do not need to be tracked separately once their letter counts are known.

For each letter, keep the largest count requested by any word in words2. This maximum is the complete requirement: a candidate meeting it contains every word in words2, and a candidate missing it fails the particular word that requested that maximum. Each word in words1 then needs only one frequency count and one comparison against the shared requirement.

Approachbuild one requirement profile, then scan the candidates

Create an array maxCount of 26 zeroes, one for each lowercase letter, because every universal word must satisfy the strongest demand for each letter.

Count the letters in each word of words2 and merge that count into maxCount using a per-letter maximum, because adding counts would demand letters that no single word requires together.

For every word a in words1, build its own 26-letter frequency array, because multiplicity matters and checking only whether a letter appears would accept too few copies.

Compare a's count with maxCount for all 26 letters and reject a as soon as one count is smaller, because that missing requirement identifies a word in words2 that a cannot contain.

Append a to the answer only if all 26 comparisons pass, because satisfying every maximum requirement is equivalent to containing every word in words2.

Complexitythe alphabet scan is constant-sized but still counted explicitly

MEASURE	BOUND	WHY
Time	O(ML + N(L + 26))	Counting every word in words2 examines each of its characters once, and merging its count scans 26 entries. Each word in words1 is counted by its characters and then compared across the same 26 entries, so no character or alphabet slot is processed more than the stated number of times.
Space	O(26) extra	The requirement array and one temporary count array each have 26 entries, so their size is constant. The returned answer is required output and is excluded from the extra-space bound; the bound does not degrade with the shape of the input.

Here N is words1.length, M is words2.length, and L is the maximum length of any input word. The alphabet size is 26.

Annotated solutionC++ · frequency aggregation and candidate filtering

CPPBuild the maximum requirement profile, then keep candidates that meet every letter count.

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
        vector<int> maxCount(26, 0);

        for (const string& b : words2) {
            vector<int> count(26, 0);
            for (char c : b) {
                count[c - 'a']++;
            }

            for (int i = 0; i < 26; i++) {
                maxCount[i] = max(maxCount[i], count[i]);
            }
        }

        vector<string> result;
        for (const string& a : words1) {
            vector<int> count(26, 0);
            for (char c : a) {
                count[c - 'a']++;
            }

            bool universal = true;
            for (int i = 0; i < 26; i++) {
                if (count[i] < maxCount[i]) {
                    universal = false;
                    break;
                }
            }

            if (universal) {
                result.push_back(a);
            }
        }

        return result;
    }
};

The key line is maxCount[i] = max(maxCount[i], count[i]). It records the strongest requirement for one letter without combining unrelated words. For example, words2 containing aa and bb requires two a characters or two b characters depending on the word, but it does not require two of both. The maximum is therefore exact rather than an approximation.