34. Word Subsets

Topic :

hashing

Difficulty :

medium

Problem Link :

link

problem statement

You are given two string arrays words1 and words2.

A string b is a subset of string a if every letter in b occurs in a 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.

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, words2.length <= 104
1 <= words1[i].length, words2[i].length <= 10
words1[i] and words2[i] consist only of lowercase English letters.
All the strings of words1 are unique.

solution

import java.io.*;
import java.util.*;
 class Word_Subsets
{
   public static void main(String args[]){
    String []words1 = {"amazon","apple","facebook","google","leetcode"};
    String []words2 = {"e","o"};
    
    System.out.println(wordSubsets(words1,words2));
    }
   static List<String> wordSubsets(String[] words1, String[] words2) {
      List<String> ans=new ArrayList<>();
        int []max_frequency_words2=new int[26];
        for(String word : words2){
            int []charFrequencyOfCurrWord=char_frequency(word);
            
            for(int i=0;i<26;i++)
            {
                max_frequency_words2[i]=Math.max(max_frequency_words2[i],charFrequencyOfCurrWord[i]);
            }
        }
        
        for(String word :words1)
        {
          int[] charFrequencyOfCurrWord=char_frequency(word);
            boolean isAns=true;
          for(int i=0;i<26;i++)
          {
              if(charFrequencyOfCurrWord[i]<max_frequency_words2[i])
              {
                 isAns=false;
                  break;
              }
            
          }
          if(isAns==true)
          ans.add(word);
        }
        
        return ans;
    }
    
    static int[] char_frequency (String s){
        int [] frequencyOfEachChar =new int[26];
        
        for(char ch :s.toCharArray()){
            frequencyOfEachChar[ch-'a']++;
        }
        
        return frequencyOfEachChar;
    }
}