Skip to main content
Talentd

Maximum Product of Word Lengths - Solution & Explanation

MediumArrayStringBit Manipulation17 min readAsked at: Amazon, Google
Practice this problem

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: 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.

Approach Overview

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).

Approach 1: Bitmask for Character Representation

This approach uses bit manipulation to represent each word with a bitmask where each bit corresponds to a character ('a' to 'z'). This allows comparison of character sets in constant time using a bitwise AND operation. If two words have no common characters, their corresponding bitmask AND result should be zero.

The solution first computes a bitmask for each word using each character's position in the alphabet. Then, it iterates through all possible pairs of words, checking if their bitmasks overlap. If they do not overlap, it means the words do not share common letters, and it calculates their length product, updating the maximum product accordingly.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N^2 + L), where N is the number of words and L is the total number of characters across all words.
Space Complexity: O(N), as we require an array to store bit masks for each word.

Try this approach in the editor →

Approach 2: Nested Loop with Set Comparison

This approach involves iterating through each pair of words, using a set to represent the characters of each word. For each pair, it checks if there are any common letters using set intersection. This method is straightforward but less efficient than bit manipulation for larger input sizes.

In this Python solution, each word is converted into a set of characters. The method then goes through each pair of words and checks for common letters using set intersection. If no common letters exist—and thereby the intersection is an empty set—it calculates their length product and updates the maximum product.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(N^2 * L) where L is the average length of the words.
Space Complexity: O(N * L) as each word is stored in a set.

Try this approach in the editor →

Approach 3: Bit Manipulation

The problem requires us to find two strings without common letters, so that their length product is maximized. We can represent each string with a binary number mask[i], where each bit of this binary number indicates whether the string contains a certain letter. If two strings do not have common letters, then the bitwise AND result of the two binary numbers corresponding to these strings is 0, that is, mask[i] \& mask[j] = 0.

We traverse each string. For the current string words[i] we are traversing, we first calculate the corresponding binary number mask[i], and then traverse all strings words[j] where j \in [0, i). We check whether mask[i] \& mask[j] = 0 holds. If it holds, we update the answer to max(ans, |words[i]| times |words[j]|).

After the traversal, we return the answer.

The time complexity is O(n^2 + L), and the space complexity is O(n). Here, n is the length of the string array words, and L is the sum of the lengths of all strings in the string array.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Bitmask for Character Representation

Time Complexity: O(N^2 + L), where N is the number of words and L is the total number of characters across all words.
Space Complexity: O(N), as we require an array to store bit masks for each word.

Nested Loop with Set Comparison

Time Complexity: O(N^2 * L) where L is the average length of the words.
Space Complexity: O(N * L) as each word is stored in a set.

Bit Manipulation—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Nested Loop with Set ComparisonO(n^2 * L)O(L)Simple baseline solution when optimizing character comparison is not required
Bitmask for Character RepresentationO(n^2)O(n)Best general solution; converts character checks into constant-time bit operations

Video Solution

Leetcode 318. Maximum Product of Word Lengths • Code with Alisha • 5,616 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Maximum Product of Word Lengths with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays