Maximum Product of Word Lengths — Solution

Problem

Given an array of words, find two words that share no common letters and return the maximum product of their lengths. If no such pair exists, return 0.

• Input: words = ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
• Output: 16
• Explanation: "abcw" (length 4) and "xtfn" (length 4) share no letters, so 4 × 4 = 16.

Counter-example: "foo" and "xtfn" both contain 'f', so they cannot be paired.

Intuition

For any pair of words, the only thing that matters is whether their character sets overlap. Since the input contains only lowercase letters, each word's set of 26 possible characters fits exactly into a 26-bit integer — one bit per letter. Checking overlap then becomes a single bitwise AND instead of scanning characters one by one, and because the masks can be precomputed once, every pair check drops to O(1).

Approach 1 — Set Comparison

Build a character set for each outer word and scan the inner word's characters to detect overlap.

1. For each index i, convert words[i] into a character set.
2. For each index j > i, check whether any character in words[j] appears in the set.
3. If no character overlaps, compute len(words[i]) × len(words[j]).
4. Return the maximum product found across all pairs.

1def maxProduct(words: list[str]) -> int:
2    max_product = 0
3    for i in range(len(words)):
4        char_set = set(words[i])
5        for j in range(i + 1, len(words)):
6            if not any(char in char_set for char in words[j]):
7                max_product = max(max_product, len(words[i]) * len(words[j]))
8    return max_product

Time: O(n² × L) — for each of the O(n²) pairs, checking overlap costs O(L) in the worst case.
Space: O(n) — a character set of at most 26 entries per word, so O(n × 26) = O(n) total.

Approach 2 — Bitmask Precomputation

Encode each word as a 26-bit integer where bit k is set if the word contains the k-th letter. Two words share no letters if and only if their bitmasks AND to zero, turning the per-pair overlap check from O(L) to O(1).

1. For each word, initialize its mask to 0, then OR in 1 << (c - 'a') for every character c.
2. Store all masks in an array alongside the words.
3. For every pair (i, j), compute masks[i] & masks[j].
4. If the result is 0 (no shared bits), update the maximum product.

1def maxProduct(words: list[str]) -> int:
2    masks = [0] * len(words)
3    for i, word in enumerate(words):
4        for char in word:
5            masks[i] |= 1 << (ord(char) - ord('a'))
6
7    max_product = 0
8    for i in range(len(words)):
9        for j in range(i + 1, len(words)):
10            if masks[i] & masks[j] == 0:  # no shared bits means no shared letters
11                max_product = max(max_product, len(words[i]) * len(words[j]))
12    return max_product

Time: O(nL + n²) — O(nL) to precompute all masks once, then O(n²) pair checks each at O(1).
Space: O(n) — one 32-bit integer mask per word.

Complexity Summary

Common Mistakes

• Missing parentheses in Java's overlap check: masks[i] & masks[j] == 0 is silently parsed as masks[i] & (masks[j] == 0) because == binds tighter than & in Java. The AND compares masks[i] against a boolean (0 or 1), not the pair's combined mask, producing wrong results with no compile error.
• Using the character index instead of a shifted bit: Writing masks[i] |= (c - 'a') sets bits 0–25 as raw values rather than positions — 'b' would set bit 1 (value 1), but so would 'a' + 1 and many other things. The correct expression is 1 << (c - 'a').
• Starting the inner loop at j = 0 instead of j = i + 1: This double-counts every pair and includes self-pairs (i, i), where the mask ANDs with itself (non-zero for any non-empty word) but the length product may still be compared. It also doubles runtime for no benefit.
• Unsigned multiplication overflow in C++: words[i].size() * words[j].size() returns size_t (unsigned). For long words the product can silently wrap, comparing as a huge number against the signed maxProduct. Cast at least one operand to int or long long before multiplying.
• Stopping at the first non-overlapping pair: The problem requires the maximum product across all valid pairs — there may be several zero-AND pairs and the first found is rarely the largest.

Related Problems

• single-number — introductory XOR/bit-manipulation problem that builds the bitwise-operator intuition used here
• counting-bits — reasoning about which bits are set in integers across a range
• number-of-1-bits — counting set bits (popcount), a natural companion to building bitmasks
• bitwise-and-of-numbers-range — bit masking applied across a numeric range rather than character sets
• find-all-duplicates-in-an-array — uses bit-level bookkeeping to track element membership, the same idea as the character-presence mask here