Skip to main content

318 - Maximum Product of Word Lengths

Difficulty: Medium | Pattern: Bit Manipulation | Company tags: Amazon, Google

Problem Statement​

Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.

Example 1:

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: "abcw" and "xtfn" share no letters: 4 × 4 = 16

Example 2:

Input: words = ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4  ("abc" and "d": 3×1? No, "d" has 1. "ab" and "cd": 2×2=4 ✓)

Approach: Bitmask per Word — O(n² + n×L)​

Key insight: Represent each word as a 26-bit integer where bit i is set if the word contains the i-th letter. Two words share no letters iff their bitmasks AND to 0.

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

Algorithm Flow​

Dry Run​

words = ["abcw","xtfn"]

  • "abcw": bits for a(0), b(1), c(2), w(22) → mask = 0b10000000000000000000000111 = some integer
  • "xtfn": bits for x(23), t(19), f(5), n(13) → different bits
  • masks[0] & masks[1] = 0 → product = 4×4 = 16 ✓

Why Bitmask?​

Checking if two sets of letters overlap naively takes O(L²) per pair. With bitmasks, it's O(1) per pair after O(L) preprocessing per word. Total: O(n×L + n²) vs O(n²×L²).

Edge Cases​

  • All words share letters → return 0
  • Single word → return 0 (no pair)
  • Words with repeated letters → bitmask handles (OR is idempotent)

Complexity​

  • Time: O(n×L + n²) where L = average word length
  • Space: O(n)