Is Maximum Product of Word Lengths easy or hard?

The problem is rated Medium difficulty. The brute force idea is straightforward, but recognizing that character presence can be encoded using bitmasks is the key optimization that interviewers expect.

Maximum Product of Word Lengths Python/Java solution

Python and Java implementations typically compute a bitmask for each word using bit shifting. After storing masks and lengths, nested loops check pairs with a bitwise AND operation. This keeps the comparison constant time and maintains O(n^2) complexity.

How to solve Maximum Product of Word Lengths in O(n^2)?

Convert every word into a 26-bit mask indicating which characters appear. Store the word length alongside the mask. Then iterate over all word pairs and check if mask[i] & mask[j] equals zero. If so, update the maximum product of their lengths.

What is the best approach for Maximum Product of Word Lengths?

The most efficient solution uses a bitmask to represent characters in each word. Each word is encoded as a 26-bit integer where each bit corresponds to a letter. Two words share no letters if their masks AND to zero. This allows pair checks in O(1) time, giving an overall O(n^2) algorithm.

Is Maximum Product of Word Lengths asked at Google/Amazon/Meta?

This problem appears frequently in interview preparation lists and has been reported in interviews at large tech companies such as Amazon, Google, and Meta. It tests knowledge of bit manipulation, string processing, and optimization of pair comparisons.

What data structure is used in Maximum Product of Word Lengths?

The optimal solution relies on integer bitmasks to represent character presence, combined with an array storing masks and word lengths. Some simpler implementations use sets for character comparison before transitioning to bit manipulation.

What is the time complexity of Maximum Product of Word Lengths?

The optimal bitmask approach runs in O(n^2) time after an O(n * L) preprocessing step to build masks, where n is the number of words and L is the average word length. Each pair comparison becomes a constant-time bitwise operation.

Description Solution Video 8:14

318. Maximum Product of Word Lengths

Medium61.7% acceptance2 companies

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: The two words can be "abcw", "xtfn".

Example 2:

Input: words = ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words can be "ab", "cd".

Example 3:

Input: words = ["a","aa","aaa","aaaa"]
Output: 0
Explanation: No such pair of words.

Constraints:

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

Asked at 2 companies

Google Amazon

Topics

8:14

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maxProduct(self, words: List[str]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

["abcw","baz","foo","bar","xtfn","abcdef"]

Input

["a","ab","abc","d","cd","bcd","abcd"]

Input

["a","aa","aaa","aaaa"]

Your code is saved on this device.Solution