Domain 2MediumCORE

Maximum Product of Word Lengths

We are given an array of strings, words. The goal is to find the maximum product of lengths between any two words in this list that do not share a common letter. If no such pair exists (i.e., every possible pair shares at least one character), we must return 0.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Bit Manipulation

318. Maximum Product of Word Lengths

Model: qwen3.5:9b
Topics: Bit Manipulation
FAANG asked: 1
Acceptance rate: 52.4%


Problem Breakdown

We are given an array of strings, words. The goal is to find the maximum product of lengths between any two words in this list that do not share a common letter. If no such pair exists (i.e., every possible pair shares at least one character), we must return 0.

Inputs: A list of lowercase English string arrays (words). Outputs: An integer representing the maximum product length, or 0 if invalid pairs don’t exist. Implicit Constraints & Edge Cases:

  • The alphabet size is fixed (26 letters). This suggests an approach based on character sets rather than raw strings for comparison.
  • Word lengths can be up to 1000, and the number of words up to 1000. A naive O(N3)O(N^3) or inefficient string intersection check could TLE if not optimized.
  • If words contains duplicates (same content), they are treated as distinct entities in the array but share letters by definition. The bitmask handles this naturally since identical masks will always intersect.

Intuition

The brute-force approach is to iterate through every pair of words (i,j)(i, j) and check if their character sets have an intersection.

  • Naive Check: For each word pair, convert strings to Sets or use set.intersection(). This takes O(L1+L2)O(L_1 + L_2) where LL is the length of the string.
  • Complexity Issue: With N=1000N=1000, we have roughly 5×1055 \times 10^5 pairs (N(N−1)2\frac{N(N-1)}{2}). If checking intersection takes time proportional to word length, total complexity becomes O(N2⋅L)O(N^2 \cdot L). While potentially acceptable given constraints, it’s not optimal.

Key Insight: We only care about which characters are present in a word, not the order or frequency of their occurrence within that specific word. Since there are only 26 lowercase English letters (‘a’ through ‘z’), we can represent each unique set of characters as an integer bitmask (an integer where the kk-th bit is set if the kk-th letter exists).

  • Optimization: Checking for common letters becomes a bitwise AND operation. If mask_i & mask_j == 0, they share no letters. This check is effectively O(1)O(1) relative to word length, bounded only by integer width (constant time on modern hardware).

Approach

  1. Preprocessing: Iterate through each string in the input array. For every character encountered, set the corresponding bit in an integer mask. Store this mask alongside the original word’s length for quick access later. We can discard duplicate characters within a single word during masking since mask |= (1 << shift) handles redundancy automatically.
  2. Pairwise Comparison: Iterate through all unique pairs of indices (i,j)(i, j) where 0≤i<j<N0 \le i < j < N.
  3. Bitwise Check: For each pair, perform the bitwise AND operation on their stored masks. If the result is zero, they are disjoint in terms of characters.
  4. Update Maximum: Calculate length[i] * length[j] and update a global maximum variable if this product exceeds the current max. Initialize the max to 0 (since valid products must be positive).

Complexity Analysis

  • Time Complexity: O(N⋅L+N2)O(N \cdot L + N^2), where NN is words.length and LL is average word length.
    • Preprocessing takes O(∑∣word∣)O(\sum |word|). Since max characters per word is 1000 but alphabet size is constant (26), the mask generation effectively caps at O(N⋅K)O(N \cdot K) where K=26K=26, making it linear with respect to input string data.
    • The nested loop runs N22\frac{N^2}{2} times, performing bitwise operations which are O(1)O(1).
  • Space Complexity: O(N)O(N) to store the masks and lengths for each word in a list or dictionary structure.

Solution

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        # Precompute bitmasks and lengths for all words
        # Each mask represents the set of characters present (bit k is 1 if char 'a'+k exists)
        masks = [] 
        for w in words:
            current_mask = 0
            length = len(w)
            for char in w:
                # Map 'a' -> bit 0, 'b' -> bit 1, ..., 'z' -> bit 25
                current_mask |= (1 << (ord(char) - ord('a')))
            masks.append((current_mask, length))
        
        max_prod = 0
        n = len(masks)
        
        # Check every pair of words for disjoint character sets
        for i in range(n):
            mask_i, len_i = masks[i]
            for j in range(i + 1, n):
                mask_j, len_j = masks[j]
                
                # If bitwise AND is zero, they share no common letters
                if (mask_i & mask_j) == 0:
                    max_prod = max(max_prod, len_i * len_j)
                    
        return max_prod

Edge Cases Handled

  • No Valid Pairs: Initialized max_prod to 0. If no disjoint pair is found during the loop iterations, it returns 0 as required by constraints and examples.
  • Duplicate Characters in Word: The bitwise OR operation (|=) ensures that if a character appears multiple times within one word (e.g., “aa”), only its corresponding bit remains set once; this does not affect correctness or length calculation.
  • Single Character Words: Handled correctly by the bitmask logic and standard integer arithmetic for product calculation.