LeetCode 318: Maximum Product of Word Lengths

Problem Restatement

We are given an array of lowercase strings words.

Return the maximum value of:

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

Function shape:

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

Examples

Example 1:

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

Output:

16

The pair can be:

"abcw", "xtfn"

They share no letters.

Their product is:

4 * 4 = 16

Example 2:

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

Output:

4

The pair can be:

"ab", "cd"

The product is:

2 * 2 = 4

Example 3:

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

Output:

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.

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.

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

For example:

word = "abc"

has bits for a, b, and c.

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

So:

mask1 & mask2 == 0

means the two words are disjoint.

Building a Mask

For each character ch, compute its bit position:

ord(ch) - ord("a")

Then turn that bit on:

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:

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:

The bitwise comparison itself is O(1).

Implementation

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.

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

For each word, start with an empty mask.

mask = 0

For every character, compute its bit position.

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

Then turn that bit on.

mask |= 1 << bit

After the mask is built, store it.

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

Now compare every pair.

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

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

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

Then update the maximum product.

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:

"abc"
"bca"
"aaabbbccc"

They all contain the same set of letters.

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

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

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: