Word Subsets — Solution in Python, Java & C++
Word Subsets solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.
Word Subsets is a medium coding problem on strings, hash table and counting, asked in Amazon, Google and Uber interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Counting
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 100001 <= word length <= 10All strings consist of lowercase English letters.
Hints for Word Subsets
Hint 1
Checking each word of
words1against each word ofwords2is too slow.Hint 2
Collapse
words2into a single requirement: for each letter, the maximum count demanded by any single word.Hint 3
Then one word of
words1is universal exactly when its letter counts dominate that requirement.
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
- Build
need[26], whereneed[c]is the largest number of times lettercappears in any single word ofwords2. - For each word of
words1, count its letters. - 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
words2instead 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 outJava
public static String[] wordSubsets(String[] words1, String[] words2) {
int[] need = new int[26];
for (String w : words2) {
int[] c = new int[26];
for (int i = 0; i < w.length(); i++) c[w.charAt(i) - 'a']++;
for (int i = 0; i < 26; i++) need[i] = Math.max(need[i], c[i]);
}
List<String> out = new ArrayList<>();
for (String w : words1) {
int[] c = new int[26];
for (int i = 0; i < w.length(); i++) c[w.charAt(i) - 'a']++;
boolean ok = true;
for (int i = 0; i < 26; i++) {
if (c[i] < need[i]) { ok = false; break; }
}
if (ok) out.add(w);
}
return out.toArray(new String[0]);
}C++
vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
vector<int> need(26, 0);
for (const string& w : words2) {
vector<int> c(26, 0);
for (char ch : w) c[ch - 'a']++;
for (int i = 0; i < 26; i++) need[i] = max(need[i], c[i]);
}
vector<string> out;
for (const string& w : words1) {
vector<int> c(26, 0);
for (char ch : w) c[ch - 'a']++;
bool ok = true;
for (int i = 0; i < 26; i++) {
if (c[i] < need[i]) { ok = false; break; }
}
if (ok) out.push_back(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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets