LeetCode Entry

916. Word Subsets

10.01.2025 medium 2025 kotlin rust

Words containing all chars of words2

916. Word Subsets medium blog post substack youtube deep-dive

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/860

Problem TLDR

Words containing all chars of words2 #medium

Intuition

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;
    }