Scale Engineer

Word Subsets

Med
#0870Time: O(N * M * (L1 + L2)), where `N` is `words1.length`, `M` is `words2.length`, `L1` is the max length of a word in `words1`, and `L2` is the max length of a word in `words2`. For each of the `N * M` pairs, we build frequency maps which takes `O(L1 + L2)` time. This is too slow for the given constraints.Space: O(L1 + L2) or O(1). Inside the loops, we create two frequency maps of size 26. Since the alphabet size is constant and the maximum word length is small, this can be considered constant auxiliary space. The space for the output list is not included.
Data structures
ArrayHash TableString

Prompt

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 = ["lc","eo"]

Output: ["leetcode"]

Example 3:

Input: words1 = ["acaac","cccbb","aacbb","caacc","bcbbb"], words2 = ["c","cc","b"]

Output: ["cccbb"]

 

Constraints:

  • 1 <= words1.length, words2.length <= 104
  • 1 <= words1[i].length, words2[i].length <= 10
  • words1[i] and words2[i] consist only of lowercase English letters.
  • All the strings of words1 are unique.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem definition into code. We iterate through each word a in words1 and, for each a, we check if it is "universal". To do this, we perform another iteration through every word b in words2 and verify if b is a subset of a. If a contains all characters for every b in words2, it's added to our result list.

Algorithm

  • Initialize an empty list universalWords.
  • For each word a in words1:
    • Set a flag isUniversal to true.
    • Create the character frequency map for a, let's call it countA.
    • For each word b in words2:
      • Create the character frequency map for b, let's call it countB.
      • Compare the maps: if for any character c, countB[c] > countA[c], then b is not a subset of a.
      • If b is not a subset of a, set isUniversal to false and break the inner loop.
    • If isUniversal is still true after checking all words in words2, add a to universalWords.
  • Return universalWords.

Walkthrough

The core of this method is a nested loop structure. The outer loop selects a word from words1, and the inner loop tests it against all words from words2.

A helper function can be used to determine if string b is a subset of string a. This function works by creating frequency maps (arrays of size 26 for lowercase English letters) for both strings. It then compares these maps. If the frequency of any character in b is greater than its frequency in a, b is not a subset of a.

If a word from words1 fails the subset test for any word in words2, we immediately know it's not universal and can move to the next word in words1.

import java.util.ArrayList;import java.util.List; class Solution {    public List<String> wordSubsets(String[] words1, String[] words2) {        List<String> result = new ArrayList<>();        for (String a : words1) {            boolean isUniversal = true;            for (String b : words2) {                if (!isSubset(a, b)) {                    isUniversal = false;                    break;                }            }            if (isUniversal) {                result.add(a);            }        }        return result;    }     private boolean isSubset(String a, String b) {        int[] countA = countFreq(a);        int[] countB = countFreq(b);        for (int i = 0; i < 26; i++) {            if (countA[i] < countB[i]) {                return false;            }        }        return true;    }     private int[] countFreq(String s) {        int[] freq = new int[26];        for (char c : s.toCharArray()) {            freq[c - 'a']++;        }        return freq;    }}

Complexity

Time

O(N * M * (L1 + L2)), where `N` is `words1.length`, `M` is `words2.length`, `L1` is the max length of a word in `words1`, and `L2` is the max length of a word in `words2`. For each of the `N * M` pairs, we build frequency maps which takes `O(L1 + L2)` time. This is too slow for the given constraints.

Space

O(L1 + L2) or O(1). Inside the loops, we create two frequency maps of size 26. Since the alphabet size is constant and the maximum word length is small, this can be considered constant auxiliary space. The space for the output list is not included.

Trade-offs

Pros

  • Simple to conceptualize and implement.

  • Directly follows the logic of the problem statement.

Cons

  • Highly inefficient due to the nested loops and repeated calculations of frequency maps.

  • Will result in a "Time Limit Exceeded" error on large test cases as specified in the problem constraints.

Solutions

class Solution {public  List<String> wordSubsets(String[] words1, String[] words2) {    int[] cnt = new int[26];    for (var b : words2) {      int[] t = new int[26];      for (int i = 0; i < b.length(); ++i) {        t[b.charAt(i) - 'a']++;      }      for (int i = 0; i < 26; ++i) {        cnt[i] = Math.max(cnt[i], t[i]);      }    }    List<String> ans = new ArrayList<>();    for (var a : words1) {      int[] t = new int[26];      for (int i = 0; i < a.length(); ++i) {        t[a.charAt(i) - 'a']++;      }      boolean ok = true;      for (int i = 0; i < 26; ++i) {        if (cnt[i] > t[i]) {          ok = false;          break;        }      }      if (ok) {        ans.add(a);      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem