Maximum Product of Word Lengths — Bitmask AND for Disjoint Letter Sets

Problem Statement#

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

Constraints:

• 2 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] consists of only lowercase English letters.

Examples:

Input:  words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: "abcw" (4) and "xtfn" (4) share no letters -> 4 * 4 = 16.
 
Input:  words = ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: "a" (1) and "bcd" (3) -> 3, or "ab" (2) and "cd" (2) -> 4. Max = 4.
 
Input:  words = ["a","aa","aaa","aaaa"]
Output: 0

Why This Problem Matters#

This is the canonical introduction to bitmask thinking in coding interviews. The naive approach checks letter overlap by intersecting two sets — O(L1 + L2) per pair, O(N^2 * L) overall. The bitmask approach precomputes a 26-bit fingerprint per word and reduces overlap checking to a single bitwise AND — O(N^2) total. Google, Amazon, and Apple use this problem because the speedup is dramatic and the code is short. Once you internalize the trick, dozens of related problems (set cover DP, subset DP, friend-circle problems) become tractable.

The Core Insight (the bit-trick)#

Each word's letter set fits in a 26-bit integer:

mask = 0, then for each character c: mask |= 1 << (c - 'a').

Two words share no letter iff their masks have no common set bit, i.e.:

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

That's it — one AND, one zero check, done. We do not care how many times each letter appears, only whether it appears at all. Bitmask is the perfect data structure for "set of distinct letters."

Why is this faster than set(word1) & set(word2)?

• The set version allocates two hashable Python objects and computes a structural intersection — dozens of ns.
• The bitmask AND is a single CPU instruction.

For a 1000-word input that's ~500K pair checks. Bitmask makes the inner loop register-fast.

Visual Dry Run (binary representation trace)#

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

Build masks (showing only relevant bits, a..z left to right):
  "abcw"   -> a,b,c,w           = 1000 0000 0000 0000 0000 0111
  "baz"    -> a,b,z             = 1000 0000 0000 0000 0000 0001 1
  "foo"    -> f,o               = ...
  "bar"    -> a,b,r             = ...
  "xtfn"   -> f,n,t,x           = ...
  "abcdef" -> a,b,c,d,e,f       = ...
 
Check pair ("abcw", "xtfn"):
  mask("abcw") & mask("xtfn")
   = (a|b|c|w) AND (f|n|t|x)
   = 0  (no common bits)
  -> disjoint! product = 4 * 4 = 16.
 
Check pair ("abcw", "abcdef"):
  mask("abcw") & mask("abcdef") -> bits at a,b,c set in both
  -> non-zero, skip.
 
Check pair ("foo", "bar"):
  mask("foo") & mask("bar")  = 0 -> product 3 * 3 = 9.
 
Best = 16.

The cardinal point: each check is one machine word AND followed by a comparison — orders of magnitude faster than character-by-character scans.

Solution (Optimal)#

Python#

class Solution:
    def maxProduct(self, words: list[str]) -> int:
        n = len(words)
        masks = [0] * n
        lengths = [0] * n
 
        for i, w in enumerate(words):
            m = 0
            for c in w:
                m |= 1 << (ord(c) - ord('a'))
            masks[i] = m
            lengths[i] = len(w)
 
        best = 0
        for i in range(n):
            for j in range(i + 1, n):
                if masks[i] & masks[j] == 0:
                    product = lengths[i] * lengths[j]
                    if product > best:
                        best = product
        return best

JavaScript#

var maxProduct = function (words) {
  const n = words.length;
  const masks = new Array(n);
  const lens = new Array(n);
 
  for (let i = 0; i < n; i++) {
    let m = 0;
    const w = words[i];
    for (let k = 0; k < w.length; k++) {
      m |= 1 << (w.charCodeAt(k) - 97);
    }
    masks[i] = m;
    lens[i] = w.length;
  }
 
  let best = 0;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if ((masks[i] & masks[j]) === 0) {
        const product = lens[i] * lens[j];
        if (product > best) best = product;
      }
    }
  }
  return best;
};

Complexity: Time O(N^2 + sum(L_i)) — quadratic pair checks plus mask building. Space O(N) for masks and lengths.

Common Mistakes#

• Operator precedence in C-family languages. masks[i] & masks[j] == 0 parses as masks[i] & (masks[j] == 0). Always wrap: (masks[i] & masks[j]) == 0.
• Forgetting to track lengths separately after deduplicating masks. Two words can share a fingerprint with different lengths — store max(length per mask) if you deduplicate.
• Using a 32-bit signed shift incorrectly. For 26 letters, 32-bit ints are fine, but watch out for sign extension in older languages.
• Building the mask inside the inner loop. That's O(N^2 * L) again — defeats the optimization.
• Returning the product of indices instead of lengths. Read the problem twice.

Interview Tips#

• State both complexities: brute-force O(N^2 * L) vs bitmask O(N^2 + sum(L)). Quantify: with N = 1000 and L = 1000, that's 10^9 vs 10^6 + 10^6 — a thousand-fold speedup.
• If the interviewer pushes for sub-quadratic: mention but don't promise. Sorting masks descending by length lets you early-exit when lens[i] * lens[j] cannot exceed best. The asymptotic stays O(N^2) but real-world wins are big.
• Bring up the related deduplication: if two words have identical masks, keep the longer one. Reduces the inner loop count for adversarial inputs.
• Highlight that this is the prototype for subset DP: TSP, set cover, and Steiner tree all start from the same "encode subsets of items as bits" idea.

Follow-up Questions#

1. Three words with no shared letters, max product of three lengths. Triple loop O(N^3), with the same AND check. Or meet in the middle for larger N.
2. Allow up to k overlapping letters. Replace mask & mask == 0 with popcount(mask & mask) <= k. Use a popcount intrinsic.
3. Stream of words; report current best on each insert. Maintain a list of (mask, length); on each new word, scan and update best in O(N).
4. Words with case sensitivity / unicode. Bitmask still works for any fixed alphabet of size <= 64 (using a 64-bit integer); for arbitrary unicode, fall back to hash sets.
5. Find the actual word pair, not just the product. Track (i, j) along with best and return the words after the loop.

Key Takeaways#

• Encode each word as a 26-bit OR mask of letter presence — a single integer fingerprint.
• Disjoint letter sets check is one bitwise AND — orders of magnitude faster than set intersection.
• Mind C-family operator precedence: always parenthesize (masks[i] & masks[j]) == 0.
• Build masks once before the pair loop; never rebuild inside.
• This pattern is the gateway drug to subset DP, TSP, set cover, and Steiner tree.
• For massive inputs, sort by length descending and prune with an early-exit check.