Word Subsets
Problem Statement
Aapko do string arrays diye gaye hain: words1 aur words2.
Ek string b, string a ka subset tab hota hai jab b ka har letter a mein hota hai, including multiplicity. Matlab, agar b mein koi letter 2 baar aata hai toh a mein bhi woh letter 2 baar hona chahiye.
For example, “wrr” “warrior” ka subset hai, lekin “world” ka subset nahi hai.
Ab, ek string a from words1 universal tab hoti hai jab words2 ki har string b uska subset hoti hai. Matlab, words2 ki saari strings b, string a ka subset honi chahiye.
Aapko words1 ka ek array return karna hai jismein saari universal strings ho. Answer kisi bhi order mein ho sakta hai.
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 = [“l”,”e”]
Output: [“apple”,”google”,”leetcode”]
Constraints:
1 <= words1.length, <= 104
1 <= words1[i].length, words2[i].length <= 10
words1[i] aur words2[i] sirf lowercase English letters se bane hote hain.
words1 ke saare strings unique hain.
Word Subsets
Preprocessing words2:
Words2 mein har letter ke liye required maximum frequency calculate karte hain. Jaise, agar words2 = ["aa", "ab"] ho, toh a aur b ke maximum frequencies yeh hongi:
a: 2 (kyunki "aa" mein 2 'a' hain)
b: 1 (kyunki "ab" mein 1 'b' hai)
Yeh ensure karta hai ki humare paas ek single frequency array ho jo words2 ke combined requirements ko represent karta hai.
Checking words1:
Har word in words1 ke liye, uske letter frequencies count karte hain. Check karte hain ki kya word maximum frequency requirements ko satisfy karta hai har letter ke liye.
Time Complexity:
Step 1: Preprocessing words2:
O(26 × |words2|): Har word mein words2 ke liye, 26 letters ki frequencies count karte hain.
Step 2: Checking words1:
O(26 × |words1|): Har word mein words1 ke liye, frequencies count karte hain aur max_frequencies ke against validate karte hain.
Total: O(26 × (|words1| + |words2|)) → Linear time!
Space Complexity:
Frequency Arrays:
O(26): 26 letters ke liye frequency arrays.
Result List:
O(|words1|) worst case mein.
Total: O(26 + |words1|).
Solution
/**
* @param {string[]} words1
* @param {string[]} words2
* @return {string[]}
*/
var wordSubsets = function(words1, words2) {
// Initialize karo maximum frequency jo har character ke liye chahiye
let maxFrequencies = new Array(26).fill(0); // Letters 'a' to 'z' ke liye
let lettersNeeded = new Set(); // Track karo jo letters chahiye
// Function to count karo character frequencies ek word mein
function countFrequencies(word) {
let frequencies = new Array(26).fill(0);
for (let c of word) {
let idx = c.charCodeAt(0) - 'a'.charCodeAt(0);
frequencies[idx]++;
}
return frequencies;
}
// Compute karo maximum frequencies from words2
for (let word of words2) {
let wordFrequencies = countFrequencies(word);
for (let i = 0; i < 26; i++) {
if (wordFrequencies[i] > maxFrequencies[i]) {
maxFrequencies[i] = wordFrequencies[i];
lettersNeeded.add(i);
}
}
}
// Convert karo lettersNeeded ko ek array mein for faster iteration
let lettersNeededArray = Array.from(lettersNeeded);
// List banane ke liye universal words ko store karne ke liye
let universalWords = [];
// Check karo har word ko words1 mein
for (let word of words1) {
let wordFrequencies = countFrequencies(word);
let isUniversal = true;
for (let i of lettersNeededArray) {
if (wordFrequencies[i] < maxFrequencies[i]) {
isUniversal = false;
break;
}
}
if (isUniversal) {
universalWords.push(word);
}
}
return universalWords;
};
Initialization:
maxFrequencies: Har character ke liye (a se z) maximum frequencies ko track karta hai.
lettersNeeded: Letters ka ek set jo chahiye.
2. countFrequencies Function:
Ye function ek word mein har character ki frequency count karta hai aur 26 size ka array return karta hai.
3. Compute Maximum Frequencies from words2:
words2 ke har word ki frequencies count karte hain.
Agar current frequency maxFrequencies se zyada hai, toh maxFrequencies ko update karte hain aur lettersNeeded set mein add karte hain.
4. Convert lettersNeeded to Array:
Faster iteration ke liye lettersNeeded set ko array mein convert karte hain.
5. Check Words in words1:
Har word in words1 ki frequencies count karte hain.
Check karte hain ki kya ye word universal hai by comparing with maxFrequencies.
Agar word universal hai, toh universalWords list mein add karte hain.
6. Return Universal Words:
Universal words ki list return karte hain jo words1 aur words2 ke combined requirements ko satisfy karte hain.
Solution
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;
class Solution {
public:
vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
// Initialize karo maximum frequency jo har character ke liye chahiye
vector<int> max_frequencies(26, 0); // Letters 'a' to 'z' ke liye
unordered_set<int> letters_needed; // Track karo jo letters chahiye
// Function to count karo character frequencies ek word mein
auto count_frequencies = [](const string& word) -> vector<int> {
vector<int> frequencies(26, 0);
for (char c : word) {
frequencies[c - 'a']++;
}
return frequencies;
};
// Compute karo maximum frequencies from words2
for (const string& word : words2) {
vector<int> word_frequencies = count_frequencies(word);
for (int i = 0; i < 26; ++i) {
if (word_frequencies[i] > max_frequencies[i]) {
max_frequencies[i] = word_frequencies[i];
letters_needed.insert(i);
}
}
}
// Convert karo letters_needed ko ek vector mein for faster iteration
vector<int> letters_needed_vec(letters_needed.begin(), letters_needed.end());
// List banane ke liye universal words ko store karne ke liye
vector<string> universal_words;
// Check karo har word ko words1 mein
for (const string& word : words1) {
vector<int> word_frequencies = count_frequencies(word);
bool is_universal = true;
for (int i : letters_needed_vec) {
if (word_frequencies[i] < max_frequencies[i]) {
is_universal = false;
break;
}
}
if (is_universal) {
universal_words.push_back(word);
}
}
return universal_words;
}
};
1. Initialization:
max_frequencies: Har character (a se z) ke liye required maximum frequency ko initialize karta hai.
letters_needed: Unordered set hai jo track karta hai ki kaunse letters chahiye.
2. count_frequencies Function:
Ye function ek word mein har character ki frequency count karta hai aur 26 size ka array return karta hai.
3. Compute Maximum Frequencies from words2:
words2 ke har word ki frequencies count karta hai.
Agar current frequency max_frequencies se zyada hai, toh max_frequencies ko update karte hain aur letters_needed set mein add karte hain.
4. Convert letters_needed to Vector:
Faster iteration ke liye letters_needed set ko vector mein convert karte hain.
5. Check Words in words1:
Har word in words1 ki frequencies count karte hain.
Check karte hain ki kya ye word universal hai by comparing with max_frequencies.
Agar word universal hai, toh universal_words list mein add karte hain.
6. Return Universal Words:
Universal words ki list return karte hain jo words1 aur words2 ke combined requirements ko satisfy karte hain.
