# 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.

## Brute Force:

**The Idea:** For each combination of words whose intersection return the empty set, return the maximum product of their lengths.

**Complexity:** O(n^2 \* m) where N is the number of words, and M is the length of a word.

```python
class Solution:
    def maxProduct(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        max_prod = 0
        for i in range(0, len(words)):
            for j in range(i + 1, len(words)):
                if set(words[i]) & set(words[j]) == set():
                    max_prod = max(len(words[i]) * len(words[j]), max_prod)
        return max_prod
```

## Optimal:

**The Idea:** Create a unique binary representation of the each word. We can do so by setting each bit for each character in the word. Then we can do the same thing as before and check if the intersection of each word (in this case there binary fingerprint), and look for the empty set, or 0.

![](https://176165416-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LoJHphwLiMOHOYPmtrx%2F-LoJHq55n17qGKUSaNW0%2F-LoJIqpVT1cu6ne-EgyP%2Fmax_product_length.png?generation=1568003869345570\&alt=media)

**Complexity:** O(2N\*M) time and O(N) space

```python
import string


class Solution:
    def maxProduct(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        char_int = {char: i for i, char in enumerate(list(string.ascii_lowercase))}
        word_map = [0] * len(words)

        for i, word in enumerate(words):
            for char in word:
                word_map[i] |= 1 << char_int[char]

        max_product = 0
        for i in range(0, len(words)):
            for j in range(i+1, len(words)):
                if not word_map[i] & word_map[j]: # O(1) processing time
                    max_product = max(max_product, len(words[i]) * len(words[j]))

        return max_product
```