Maximum Product of Word Lengths: Bitmask Intersection

318. Maximum Product of Word Lengths gives you an array of strings and asks for the maximum value of len(words[i]) * len(words[j]) where the two words share no common letters. If no such pair exists, return 0.

For example, given ["abcw","baz","foo","bar","xtfn","abcdef"], the answer is 16. The words "abcw" and "xtfn" have no letters in common, and 4*4=16 is the largest such product you can form.

The approach: bitmask as a letter set

The key question is how to check whether two words share a letter without re-scanning both words every time you compare a pair. If you check pairs naively by scanning character by character, that comparison costs O(L) per pair where L is the average word length. You can do it in O(1) per pair instead.

The trick is to represent each word as a 26-bit integer, one bit per letter of the alphabet. Bit k is set if the (k+1)-th letter appears in the word. So bit 0 represents 'a', bit 1 represents 'b', and so on up to bit 25 for 'z'. You build this mask by ORing in 1 << (ord(c) - ord('a')) for each character in the word.

Once you have the masks, checking whether two words share any letter is a single bitwise AND. If mask[i] & mask[j] == 0, no bit is set in both, which means no letter appears in both words. This is the intersection test. Precompute all n masks in one pass, then check all n*(n-1)/2 pairs.

def maxProduct(words: list[str]) -> int:
    masks = [0] * len(words)
    for i, word in enumerate(words):
        for c in word:
            masks[i] |= 1 << (ord(c) - ord('a'))
    best = 0
    for i in range(len(words)):
        for j in range(i + 1, len(words)):
            if masks[i] & masks[j] == 0:
                best = max(best, len(words[i]) * len(words[j]))
    return best

Complexity

The precomputation loop visits every character across all words once, costing O(total chars). The pair loop visits all n*(n-1)/2 pairs, each in O(1) with the bitmask AND, costing O(n^2). Space is O(n) for the masks array.

The building blocks

This problem is built on two reusable ideas.

Bitmask representation of sets. When your set has at most 26 (or 32, or 64) elements and you only care about membership, a single integer is enough. Each element corresponds to a bit position. Adding an element is mask |= 1 << k. Checking membership is mask & (1 << k). Checking intersection is mask_a & mask_b. You see the same "letter presence in 26 bits" encoding in problems like group anagrams and valid anagram, where it replaces a frequency array.

Bitwise AND as intersection check. a & b == 0 means the two sets are disjoint. This single expression replaces an O(26) loop comparing letter counts. The AND is zero if and only if no bit position is 1 in both operands simultaneously.

Edge cases

• All words share all letters: every pair has a non-zero AND. You never update best, and you return 0. Correct.
• One-character words: a word like "a" has mask 1. It can only pair with words that have bit 0 unset. The logic handles this without special casing.
• Words with repeated letters: a word like "aab" generates the same mask as "ab", because OR is idempotent. Repeated letters don't set any extra bits or cause double-counting.
• Single word in the array: the inner loop range(i + 1, len(words)) never executes when i == 0 and len(words) == 1, so best stays 0. Correct, since you need two distinct words to form a product.

From understanding to recall

The entire solution flows from one insight: mask[i] & mask[j] == 0 is the no-common-letters test. Once you know that, the rest follows. You need a mask per word, so you precompute them. You need the best product over all valid pairs, so you scan all pairs. Nothing surprising.

In an interview, the part worth internalizing is the mask construction: masks[i] |= 1 << (ord(c) - ord('a')). That expression lets you collapse a word's entire character set into one integer. If you have that expression automatic, the rest of the solution assembles itself around it.

Spaced repetition locks it in. You write the solution from scratch at increasing intervals, focusing on that one line each time. After a few reps, the encoding is no longer something you derive -- it's something you just write.

Related posts

• Single Number - The foundational XOR trick that introduces bitwise thinking for set membership
• Number of 1 Bits - Working with individual bits and understanding what each position means
• XOR Cancellation Pattern - A broader look at how XOR-based bit manipulation solves set problems efficiently