Buttercola: Leetcode: Maximum Product of Word Lengths

Buttercola: Leetcode: 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.

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Understand the problem:
The problem is a little bit ambiguous.  The two words used to calculate the product of length must not share any common characters. e.g. word1 = abc, word2 = bcd, the product is 0 not 1, because they share common chars. 

The most straight-forward way to solve this problem is to pick up any two words, and check if they have common characters. If not, then calculate the maximum product of the length. 

Now let's analyze the complexity in time. Suppose the number of words is n, and average word length is m. So the time complexity for the  brute-force solution is O(n^2 * m). 

A better approach using bit manipulation:
Now let's think can we reduce the time complexity when we check the intersection of two words? 

Since each word contains 26 characters in lower case only. We can use a bit map to encode the string. Since we only need 26 bits for a word, it is enough to use an integer to encode a string. 

Read full article from Buttercola: Leetcode: Maximum Product of Word Lengths