class Solution(object): def maxProduct(self, words): maxProduct = 0 binaryWords =  for word in words: binaryWords.append(self.wordToBinary(word)) for i in xrange(len(words)): for j in xrange(i+1,len(words)): #If words do not contain like characters if(not (binaryWords[i] & binaryWords[j])): maxProduct = max(maxProduct, len(words[i]) * len(words[j])) return maxProduct def wordToBinary(self,word): num = 0 for char in word: num |= (1 << ord(char)-ord('a')) return num
The only trick to this problem is finding out how to efficiently determine whether or not two words share any common letters. In order to do this, we create a new array to contain binary representation of the words. For example, the right-most bit would act as a switch to represent whether or not the word contains an 'a', the bit to the left of that a 'b', and so forth. Once our strings are represented as numbers, we can apply bitwise and (&) to any two words to find out if they share any letters in common. If the result of the & statement is 0, the two binary representations of our words do not share any common 1s. Below is an example:
binary representation: 11 or 0011
binary representation: 1100
0011 & 1100 = 0, therefor these two words do not share any common letters.
Once you've figured that out, the rest is just a matter of looping through all the words and multiplying the lengths of the ones that satisfy the above condition, while keeping track of the max.