Word Subsets — Medium Problem & Solution

Problem statement

String b is a subset of string a if every letter of b occurs in a at least as many times as it occurs in b.

A word in words1 is universal if every word in words2 is a subset of it. Return all universal words, in their original order.

Example 1

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output: ["facebook","google","leetcode"]

Example 2

Input: words1 = ["codekairo","kairo","code"], words2 = ["ko","a"]
Output: ["codekairo","kairo"]
Explanation: "code" has no a or k... it lacks both letters of "ko" beyond the o.

Example 3

Input: words1 = ["aaa","bbb"], words2 = ["aa"]
Output: ["aaa"]

Constraints

• 1 <= words1.length, words2.length <= 10000
• 1 <= word length <= 10
• All strings consist of lowercase English letters.

How to solve Word Subsets

Being a superset of every word in words2 is the same as being a superset of their per-letter maximum. Collapsing words2 into one 26-slot requirement turns the whole problem into a single comparison per candidate.

Approach

1. Build need[26], where need[c] is the largest number of times letter c appears in any single word of words2.
2. For each word of words1, count its letters.
3. Keep the word when count[c] >= need[c] for all 26 letters.

Why it works

The subset relation is per-letter and per-word, so satisfying every word at once means meeting each letter's largest single demand. Taking a maximum (not a sum) is the key: ["lo","eo"] needs one l, one e and one o, not two os.

Complexity

• Time — O(total length of both lists)
• Space — O(1) — two 26-slot arrays

Pitfalls

• Summing the counts across words2 instead of taking the maximum over-demands repeated letters.
• Comparing word lengths rather than per-letter counts accepts words with the right size but the wrong letters.

Reference solution

Python

from typing import List

def wordSubsets(words1: List[str], words2: List[str]) -> List[str]:
    need = [0] * 26
    for w in words2:
        c = [0] * 26
        for ch in w:
            c[ord(ch) - 97] += 1
        for i in range(26):
            need[i] = max(need[i], c[i])
    out = []
    for w in words1:
        c = [0] * 26
        for ch in w:
            c[ord(ch) - 97] += 1
        if all(c[i] >= need[i] for i in range(26)):
            out.append(w)
    return out

JavaScript

var wordSubsets = function(words1, words2) {
    var counts = function(w) {
        var c = [];
        for (var t = 0; t < 26; t++) c.push(0);
        for (var i = 0; i < w.length; i++) c[w.charCodeAt(i) - 97]++;
        return c;
    };
    var need = [];
    for (var u = 0; u < 26; u++) need.push(0);
    for (var j = 0; j < words2.length; j++) {
        var c2 = counts(words2[j]);
        for (var k = 0; k < 26; k++) {
            if (c2[k] > need[k]) need[k] = c2[k];
        }
    }
    var out = [];
    for (var m = 0; m < words1.length; m++) {
        var c1 = counts(words1[m]);
        var ok = true;
        for (var p = 0; p < 26; p++) {
            if (c1[p] < need[p]) { ok = false; break; }
        }
        if (ok) out.push(words1[m]);
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Make Three Strings Equal Medium
• Number of Ways to Divide a Long Corridor Medium
• Maximum Number of Non-overlapping Palindrome Substrings Medium
• Count Number of Texts Medium
• Delete Characters to Make Fancy String Medium
• Count Number of Homogenous Substrings Medium