Maximum Product of Word Lengths - Video Solutions

Problem Overview: You receive an array of lowercase words. The task is to choose two words that share no common characters and maximize the product of their lengths. If every pair shares at least one character, the result is 0.

Approach 1: Nested Loop with Set Comparison (Time: O(n^2 * L), Space: O(L))

The straightforward strategy compares every pair of words. For each word, build a set of characters, then iterate through all pairs using a nested loop. For each pair, check if the two sets intersect. If they share no characters, compute len(word1) * len(word2) and update the maximum product.

This method works because set membership and intersection checks are fast in practice, but the algorithm still evaluates all n^2 pairs. Each comparison may scan up to L characters depending on the implementation. This approach is easy to implement and good for understanding the core constraint: verifying that two strings share no characters.

Approach 2: Bitmask for Character Representation (Time: O(n^2), Space: O(n))

The optimized approach converts each word into a 26‑bit integer mask. Each bit represents whether a character from 'a' to 'z' appears in the word. For example, if a word contains a and c, the mask will have bits 0 and 2 set.

Once every word has a bitmask, compare pairs using a single bitwise operation. If mask[i] & mask[j] == 0, the words share no characters. Compute the product of their lengths and track the maximum. The key insight: bitwise AND instantly detects shared characters without scanning strings.

Mask creation takes O(n * L), and pair comparisons take O(n^2). Each check is constant time due to bit manipulation. This dramatically reduces overhead compared with repeated set checks. The input itself is stored in an array, and only one mask per word is required.

Recommended for interviews: Start by explaining the nested loop approach to demonstrate understanding of the constraint. Then transition to the bitmask optimization. Interviewers typically expect the bitmask solution because it converts character comparisons into constant‑time bit operations while keeping the overall complexity at O(n^2).