Maximum Product of Word Lengths — Problem & Solution
Maximum Product of Word Lengths solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Product of Word Lengths is a medium coding problem on arrays, strings and bit manipulation, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Bit Manipulation
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array of strings words, return the maximum value of length(words[i]) * length(words[j]) over pairs that share no common letter. If no such pair exists, return 0.
Example 1
Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: "abcw" and "xtfn" share nothing.
Example 2
Input: words = ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Example 3
Input: words = ["a","aa","aaa"]
Output: 0
Constraints
1 <= words.length <= 201 <= words[i].length <= 10words[i] consists of lowercase English letters.
Hints for Maximum Product of Word Lengths
Hint 1
Comparing letter sets directly is slow — encode each word as a 26-bit mask instead.
Hint 2
Two words share a letter exactly when the AND of their masks is non-zero.
Hint 3
Then the pairwise scan is a couple of integer operations per pair.
How to solve Maximum Product of Word Lengths
Encode each word as a 26-bit letter mask; two words share no letter iff the AND of their masks is zero.
Approach
- Build a mask per word.
- For each pair with
masks[i] & masks[j] == 0, update the best product of lengths.
Why it works
The mask captures the letter set, and set intersection becomes a single AND, so each pair costs O(1).
Complexity
- Time —
O(L + n²) - Space —
O(n)
Pitfalls
- Keep only the longest word per distinct mask to shrink the pair loop.
Reference solution
Python
def maxProduct(words) -> int:
masks = []
for w in words:
mask = 0
for ch in w:
mask |= 1 << (ord(ch) - 97)
masks.append(mask)
best = 0
for i in range(len(words)):
for j in range(i + 1, len(words)):
if masks[i] & masks[j] == 0:
best = max(best, len(words[i]) * len(words[j]))
return bestJava
public static int maxProduct(String[] words) {
int[] masks = new int[words.length];
for (int i = 0; i < words.length; i++) {
int mask = 0;
for (int j = 0; j < words[i].length(); j++) mask |= 1 << (words[i].charAt(j) - 'a');
masks[i] = mask;
}
int best = 0;
for (int i = 0; i < words.length; i++) {
for (int j = i + 1; j < words.length; j++) {
if ((masks[i] & masks[j]) == 0) {
best = Math.max(best, words[i].length() * words[j].length());
}
}
}
return best;
}C++
int maxProduct(vector<string>& words) {
vector<int> masks(words.size(), 0);
for (size_t i = 0; i < words.size(); i++) {
int mask = 0;
for (char c : words[i]) mask |= 1 << (c - 'a');
masks[i] = mask;
}
int best = 0;
for (size_t i = 0; i < words.size(); i++) {
for (size_t j = i + 1; j < words.size(); j++) {
if ((masks[i] & masks[j]) == 0) {
int product = (int) (words[i].size() * words[j].size());
if (product > best) best = product;
}
}
}
return best;
}JavaScript
var maxProduct = function(words) {
const masks = [];
for (let i = 0; i < words.length; i++) {
let mask = 0;
for (let j = 0; j < words[i].length; j++) mask |= 1 << (words[i].charCodeAt(j) - 97);
masks.push(mask);
}
let best = 0;
for (let i = 0; i < words.length; i++) {
for (let j = i + 1; j < words.length; j++) {
if ((masks[i] & masks[j]) === 0) {
const product = words[i].length * words[j].length;
if (product > best) best = product;
}
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.