WORDPRD-Editorial

editorial
, , , ,
1

PROBLEM LINK:

WORDPRD

Author: aniket_111
Tester: sahoomirnalin
Editorialist: aniket_111

DIFFICULTY:

MEDIUM

PREREQUISITES:

bitset, hashmap, array, min-max

PROBLEM:

Chef has been given an array word consisting of N strings, he wants to return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. Which means the strings word[i] and word[j] contain no common characters. If no such two words exist in the given array, Chef should return 0.

EXPLANATION

We need to find all the pair of words such that no common letter exists between them. The final answer will be max(word[i].size() * word[j].size()) chosen from all pairs (word[i], word[j]) such that they don’t have any letter in common.

One way to efficiently check if two words have a letter in common is to just create an hashmap of size 26 and map each 26 letter of both the words as true/false depending upon whether it occurs in the word or not.

Finally, we can iterate over this map and check if there’s any letter that occurs in both the words and if it does, we know that the word have atleast 1 letter in common.

Here, I have used bitset<26> instead of hashmap or boolean array for space efficiency.

TIME COMPLEXITY

Time complexity is O(n) or O(n*(N+n)), where n is the length of words and N is the average length of words

SOLUTIONS:

#include <iostream>
#include<vector>
using namespace std;

  int set_bit(string& str){
     int mybits = 0;
     for (char c : str){
       mybits |= (1 << (c-'a'));
       if ((mybits == 0x3FFFFFF)) break;
     }
     return mybits;
   }

   int maxProduct(vector<string>& words) {
     int m_val = 0, w_size = words.size();
     int m[w_size], m_w_size[w_size];
    
     for(int i = 0; i < w_size; i++) {
       m[i] = set_bit(words[i]);
       m_w_size[i] = words[i].size();
     }

     for (int i = 0; i < w_size; i++) 
         for (int j = i+1; j < w_size; j++) 
            if ((m[i] & m[j])==0) 
                m_val = max((int)(m_w_size[i] * m_w_size[j]), m_val);

    return m_val;
  }


int main(){
int t,n,ans;
string word;
vector<string> v;
cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>word;
            v.push_back(word);
        }
        ans=maxProduct(v);
        cout<<ans<<endl;
    }
    return 0;
}