Leetcode Problem - Word Subsets

Problem Statement

You are given two string arrays words1 and words2. A string b is a subset of string an if every letter in b occurs in an 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.

What is the problem in simple terms?

• There are two strings array words1 and words2.
• For a string wordString in words1 should be called a universal string if all the strings in words2 are a subset of the wordString.
• Also, the subset doesn't follow the order of characters or elements.

Solution Writing

Approach 1 [TLE]

• As we have to find the universal strings in words1 and hence, for each wordString in words1 we can traverse all the strings of words2 to check if all the strings are subsets of wordString or not.
• If all strings are a subset of wordString then it will be considered as a universal string.

vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {   
        vector<string> ans;

        for(auto &wordString:words1){
            // counting characters of string in words1
            unordered_map<char,int> counter1;
            for(auto &x:wordString){
                counter1[x]++;
            }

            bool add=true;
            // checking if the strings of word2 are subset of wordString or not
            for(auto &word:words2){
                unordered_map<char,int> counter2;
                for(auto &x:word){
                    counter2[x]++;
                }

                for(auto &letter_count:counter2){
                    // checking if wordString has greater count of characters
                    // or not
                    if(counter1[letter_count.first]<letter_count.second){
                        add=false;
                        break;
                    }
                }

                if(!add){
                    break;
                }

            }

            if(add){
                // wordString is a universal string
                ans.push_back(wordString);
            }
        }
        return ans;
    }

Approach -2

• Above approach can be optimized by removing iterations of words2 for each wordString of words1.
• For a string s1 to be a subset of string s2 the only thing that's needed to be checked is whether for each character ch present in s1 the number of count of ch in s2 must be greater than or equal to s1.
• For example, let s1 = "acc", now it will be a subset of another string s₂ only if string s₂ has count of 'a' greater than or equal to 1 and a count of 'c' greater than or equal to 2.
• So, now for our problem if we traverse all the strings in the words2 array and store the maximum count of all the characters present in the strings.
• Let's say storeCount contains a maximum count of a character in the strings of words.
• Now, our task is to only count the character of each wordString in words1 and for each character ch present in storeCount check if the count of ch in in wordString should be greater than storeCount[ch].
• All the wordString which satisfies the above condition is considered as a universal string.

vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
        unordered_map<char,int> store;
        for(auto &word:words2){

            unordered_map<char,int> counter;
            for(auto &x:word){
                counter[x]++;
                store[x]=max(store[x],counter[x]);
                // storing maximum count of each character
            }

        }

        vector<string> ans;

        for(auto &wordString:words1){
            unordered_map<char,int> counter;
            for(auto &x:wordString){
                counter[x]++;
            }
            bool add=true;

            for(auto &letter_count:store){
                // checking whether wordString has greater count of characters or not
                // if not for any character then leave it
                if(counter[letter_count.first]<letter_count.second){
                    add=false;
                    break;
                }
            }
            if(add){
                // wordString is a universal string
                ans.push_back(wordString);
            }
        }
        return ans;
    }

That's all Thanks for reading !