# LeetCode 318: Maximum Product of Word Lengths

## Problem Restatement

We are given an array of lowercase strings `words`.

Return the maximum value of:

```python
len(words[i]) * len(words[j])
```

where the two words do not share any common letters.

If no such pair exists, return `0`.

The official constraints include `2 <= words.length <= 1000`, `1 <= words[i].length <= 1000`, and each word contains only lowercase English letters.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A list of lowercase words |
| Output | Maximum product of lengths |
| Pair rule | The two words must share no common letters |
| If no valid pair exists | Return `0` |

Function shape:

```python
def maxProduct(words: list[str]) -> int:
    ...
```

## Examples

Example 1:

```python
words = ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
```

Output:

```python
16
```

The pair can be:

```python
"abcw", "xtfn"
```

They share no letters.

Their product is:

```python
4 * 4 = 16
```

Example 2:

```python
words = ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
```

Output:

```python
4
```

The pair can be:

```python
"ab", "cd"
```

The product is:

```python
2 * 2 = 4
```

Example 3:

```python
words = ["a", "aa", "aaa", "aaaa"]
```

Output:

```python
0
```

Every word contains `a`, so no valid pair exists.

## First Thought: Compare Sets

For each word, we can build a set of its letters.

Then compare every pair of sets.

```python
set(words[i]).isdisjoint(set(words[j]))
```

This works.

But building and comparing sets repeatedly adds overhead.

Since there are only 26 lowercase English letters, we can encode each word's letters inside one integer.

## Key Insight

Use a 26-bit mask.

Each bit represents one letter.

| Letter | Bit |
|---|---:|
| `a` | `0` |
| `b` | `1` |
| `c` | `2` |
| ... | ... |
| `z` | `25` |

For a word, turn on the bit for every character.

For example:

```python
word = "abc"
```

has bits for `a`, `b`, and `c`.

If two words share no letters, their masks have no common `1` bits.

So:

```python
mask1 & mask2 == 0
```

means the two words are disjoint.

## Building a Mask

For each character `ch`, compute its bit position:

```python
ord(ch) - ord("a")
```

Then turn that bit on:

```python
mask |= 1 << (ord(ch) - ord("a"))
```

Repeated letters do not matter.

The word `"foo"` has the same mask as `"fo"` because we only care whether a letter exists, not how many times it appears.

## Algorithm

1. Convert each word into a bit mask.
2. Store each word's length.
3. Compare every pair of words.
4. If two masks have bitwise AND equal to `0`, they share no letters.
5. Update the answer with the product of their lengths.
6. Return the answer.

## Correctness

Each word mask contains exactly the letters present in that word.

For any two words, a letter appears in both words exactly when the corresponding bit is set in both masks. Therefore, the bitwise AND of the two masks is nonzero exactly when the two words share at least one letter.

So the condition:

```python
masks[i] & masks[j] == 0
```

is true exactly for valid pairs.

The algorithm checks every pair of words. For every valid pair, it computes the product of their lengths and keeps the maximum value.

Therefore, the returned answer is the maximum product among all pairs that share no common letters. If no valid pair exists, the answer remains `0`.

## Complexity

Let:

| Symbol | Meaning |
|---|---|
| `n` | Number of words |
| `L` | Total number of characters across all words |

| Metric | Value | Why |
|---|---:|---|
| Time | `O(L + n^2)` | Build all masks, then compare every pair |
| Space | `O(n)` | Store one mask and one length per word |

The bitwise comparison itself is `O(1)`.

## Implementation

```python
class Solution:
    def maxProduct(self, words: list[str]) -> int:
        n = len(words)

        masks = [0] * n
        lengths = [0] * n

        for i, word in enumerate(words):
            mask = 0

            for ch in word:
                bit = ord(ch) - ord("a")
                mask |= 1 << bit

            masks[i] = mask
            lengths[i] = len(word)

        answer = 0

        for i in range(n):
            for j in range(i + 1, n):
                if masks[i] & masks[j] == 0:
                    answer = max(answer, lengths[i] * lengths[j])

        return answer
```

## Code Explanation

We create arrays for masks and lengths.

```python
masks = [0] * n
lengths = [0] * n
```

For each word, start with an empty mask.

```python
mask = 0
```

For every character, compute its bit position.

```python
bit = ord(ch) - ord("a")
```

Then turn that bit on.

```python
mask |= 1 << bit
```

After the mask is built, store it.

```python
masks[i] = mask
lengths[i] = len(word)
```

Now compare every pair.

```python
for i in range(n):
    for j in range(i + 1, n):
```

If the bitwise AND is zero, the words share no letters.

```python
if masks[i] & masks[j] == 0:
```

Then update the maximum product.

```python
answer = max(answer, lengths[i] * lengths[j])
```

Finally return the best value found.

## Compressed Mask Optimization

Several words can have the same mask.

For example:

```python
"abc"
"bca"
"aaabbbccc"
```

They all contain the same set of letters.

For each mask, we only need the longest word with that mask.

```python
class Solution:
    def maxProduct(self, words: list[str]) -> int:
        best_length = {}

        for word in words:
            mask = 0

            for ch in word:
                mask |= 1 << (ord(ch) - ord("a"))

            best_length[mask] = max(
                best_length.get(mask, 0),
                len(word),
            )

        masks = list(best_length.keys())
        answer = 0

        for i in range(len(masks)):
            for j in range(i + 1, len(masks)):
                if masks[i] & masks[j] == 0:
                    answer = max(
                        answer,
                        best_length[masks[i]] * best_length[masks[j]],
                    )

        return answer
```

This can reduce pair checks when many words share the same character set.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.maxProduct(
        ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
    ) == 16

    assert s.maxProduct(
        ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
    ) == 4

    assert s.maxProduct(
        ["a", "aa", "aaa", "aaaa"]
    ) == 0

    assert s.maxProduct(
        ["ab", "cd"]
    ) == 4

    assert s.maxProduct(
        ["abcd", "efgh", "aef"]
    ) == 16

    assert s.maxProduct(
        ["abc", "def", "ghij", "ad"]
    ) == 12

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Finds maximum disjoint pair |
| Mixed prefixes | Valid pair may be shorter than the longest word |
| All share one letter | Returns `0` |
| Two disjoint words | Minimal pair case |
| Long disjoint words | Checks larger product |
| Multiple candidates | Chooses maximum product |