318. Maximum Product of Word Lengths

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".

Example 2:

Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".

Example 3:

Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.

Solution:

The pain point here is to check if two words share common letters. 

My solution is treat each word as a binary with 26 digits. Each digit corresponding to a letter, if a word contains the letter, set the digit to 1, if not set the digit to 0.

If two words share common letters, they must have one common digit. If they don't share common letters, the bitwise and of two binary will be 0.

Time complexity= time to build the binary array + time to get maximum product= O(m*n+n^2) 

m is the longest string length among all words, and n is the length of array.

 public int maxProduct(String[] words) {  
     int[] vals=new int[words.length];  
     for(int i=0;i<words.length;i++){  
       vals[i]=getVal(words[i]);  
     }  
     int res=0;  
     for(int i=0;i<vals.length;i++){  
       for(int j=i+1;j<vals.length;j++){  
         if((vals[i] & vals[j])==0) res=Math.max(res,words[i].length()*words[j].length());  
       }  
     }  
     return res;  
   }  
   public int getVal(String word){  
     int[] letter=new int[26];  
     for(int i=0;i<word.length();i++) letter[word.charAt(i)-'a']++;  
     int val=0;  
     int factor=1;  
     for(int i=0;i<26;i++){  
       if(letter[i]>0) val+=factor;  
       factor*=2;  
     }  
     return val;  
   }