Calculate the maximum frequency of words2, then filter words1.
Approach
how short can it be?
Complexity
Time complexity: $$O(n)$$
Space complexity: $$O(n)$$
Code
fun wordSubsets(words1: Array<String>, words2: Array<String>) = buildList {
val f2 = IntArray(26)
fun Array<String>.f() = asSequence().map { w ->
val f = IntArray(26); for (c in w) f[c - 'a']++; f to w
}
for ((f, w) in words2.f()) for (i in 0..<26) f2[i] = max(f2[i], f[i])
for ((f, w) in words1.f()) if ((0..<26).all { f2[it] <= f[it] }) add(w)
}
pub fn word_subsets(words1: Vec<String>, words2: Vec<String>) -> Vec<String> {
let mut f2 = vec![0; 26];
let f = |w: &String| { let mut f = vec![0; 26];
for c in w.bytes() { f[(c - b'a') as usize] += 1 }; f };
for w in words2.iter() {
let f = f(w); for i in 0..26 { f2[i] = f2[i].max(f[i]) } }
words1.into_iter().filter(|w| {
let f = f(w); (0..26).all(|i| f2[i] <= f[i]) }).collect()
}
vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
int f2[26] = {0}; vector<string> res;
for (auto &w: words2) {
int f[26] = {0}; for (char c: w) f2[c - 'a'] = max(f2[c - 'a'], ++f[c - 'a']);
}
for (auto &w: words1) {
int f[26] = {0}; for (char c: w) ++f[c - 'a'];
for (int i = 0; i < 26; ++i) if (f2[i] > f[i]) goto out;
res.push_back(w); out:
} return res;
}
Thanks for reading DMITRII’s Substack! Subscribe for free to receive new posts and support my work.
