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

![](/files/-LoJIqpVT1cu6ne-EgyP)

**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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/318-maximum-product-of-word-lengths.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.