Maximum Product of Word Lengths solution and explanation
Google
9 more videos on this problem
Leetcode 318. Maximum Product of Word LengthsCode with Alisha · 8:14 · 5K views
Maximum Product of Word Lengths | Leetcode 318 | Live coding session | Bits ManipulationCoding Decoded · 9:57 · 5K views
Maximum Product of Word Lengths | LeetCode 318 | C++, PythonKnowledge Center · 20:40 · 4K views
Maximum Product of Word Lengths | LeetCode 318 | Coders CampCoders Camp · 11:11 · 1K views
Maximum Product of Word Lengths | Bits Manipulation | 318 LeetCode | Day 27CodeWithSunny · 17:46 · 1K views
Leetcode - Maximum Product of Word Lengths (Python)Timothy H Chang · 6:47 · 1K views
LeetCode 318. Maximum Product of Word LengthsHappy Coding · 12:05 · 1K views
318. Maximum Product of Word Lengths (Leetcode Medium)Programming Live with Larry · 18:44 · 1K views
Maximum Product of Word Lengths | Bits Manipulation | LeetCode 318Java2Novice · 8:58 · 644 views
Daily Leetcode #789: May 29, 2022 - 318. Maximum Product of Word LengthsProgramming Live with Larry · 11:37 · 372 views
The problem
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 <= 10001 <= words[i].length <= 1000words[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.
class Solution:
def maxProduct(self, words) -> int:
n = len(words)
masks = [0] * n
max_product = 0
for i, word in enumerate(words):
for char in word:
masks[i] |= 1 << (ord(char) - ord('a'))
for i in range(n):
for j in range(i + 1, n):
if masks[i] & masks[j] == 0:
max_product = max(max_product, len(words[i]) * len(words[j]))
return max_productpublic class Solution {
public int maxProduct(String[] words) {
int n = words.length;
int[] masks = new int[n];
int maxProduct = 0;
for (int i = 0; i < n; i++) {
for (char c : words[i].toCharArray()) {
masks[i] |= 1 << (c - 'a');
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if ((masks[i] & masks[j]) == 0) {
maxProduct = Math.max(maxProduct, words[i].length() * words[j].length());
}
}
}
return maxProduct;
}
}#include <vector>
#include <string>
#include <iostream>
using namespace std;
int maxProduct(vector<string>& words) {
vector<int> masks(words.size(), 0);
int maxProduct = 0;
for (int i = 0; i < words.size(); ++i) {
for (char c : words[i]) {
masks[i] |= 1 << (c - 'a');
}
}
for (int i = 0; i < words.size(); ++i) {
for (int j = i + 1; j < words.size(); ++j) {
if ((masks[i] & masks[j]) == 0) {
maxProduct = max(maxProduct, int(words[i].size() * words[j].size()));
}
}
}
return maxProduct;
}var maxProduct = function(words) {
const n = words.length;
const masks = new Array(n).fill(0);
let maxProduct = 0;
for (let i = 0; i < n; i++) {
for (const char of words[i]) {
masks[i] |= 1 << (char.charCodeAt(0) - 'a'.charCodeAt(0));
}
}
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if ((masks[i] & masks[j]) === 0) {
maxProduct = Math.max(maxProduct, words[i].length * words[j].length);
}
}
}
return maxProduct;
};#include<stdio.h>
#include<string.h>
int maxProduct(char **words, int wordsSize) {
int masks[wordsSize];
memset(masks, 0, sizeof(masks));
for (int i = 0; i < wordsSize; i++) {
for (int j = 0; words[i][j]; j++) {
masks[i] |= 1 << (words[i][j] - 'a');
}
}
int maxProduct = 0;
for (int i = 0; i < wordsSize; i++) {
for (int j = i + 1; j < wordsSize; j++) {
if ((masks[i] & masks[j]) == 0) {
int product = strlen(words[i]) * strlen(words[j]);
if (product > maxProduct) {
maxProduct = product;
}
}
}
}
return maxProduct;
}public class Solution {
public int MaxProduct(string[] words) {
int n = words.Length;
int[] masks = new int[n];
int maxProduct = 0;
for (int i = 0; i < n; i++) {
foreach (char c in words[i]) {
masks[i] |= 1 << (c - 'a');
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if ((masks[i] & masks[j]) == 0) {
maxProduct = Math.Max(maxProduct, words[i].Length * words[j].Length);
}
}
}
return maxProduct;
}
}Each word is represented as a bitmask in a list, where each bit set represents a character present in the word. The solution then evaluates all pairs of words, using bitwise AND to identify if there are any common letters, and calculates and updates the maximum product of their lengths accordingly.
Time Complexity: O(N^2 + L)
Space Complexity: O(N)
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.
class Solution:
def maxProduct(self, words) -> int:
max_product = 0
sets = [set(word) for word in words]
for i in range(len(words)):
for j in range(i + 1, len(words)):
if not (sets[i] & sets[j]):
max_product = max(max_product, len(words[i]) * len(words[j]))
return max_productimport java.util.*;
public class Solution {
public int maxProduct(String[] words) {
int n = words.length;
int maxProduct = 0;
Set<Character>[] sets = new HashSet[n];
for (int i = 0; i < n; i++) {
sets[i] = new HashSet<>();
for (char c : words[i].toCharArray()) {
sets[i].add(c);
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
boolean conflict = false;
for (char c : words[j].toCharArray()) {
if (sets[i].contains(c)) {
conflict = true;
break;
}
}
if (!conflict) {
maxProduct = Math.max(maxProduct, words[i].length() * words[j].length());
}
}
}
return maxProduct;
}
}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.
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.
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.
function maxProduct(words: string[]): number {
const n = words.length;
const mask: number[] = Array(n).fill(0);
let ans = 0;
for (let i = 0; i < n; ++i) {
for (const c of words[i]) {
mask[i] |= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0));
}
for (let j = 0; j < i; ++j) {
if ((mask[i] & mask[j]) === 0) {
ans = Math.max(ans, words[i].length * words[j].length);
}
}
}
return ans;
}func maxProduct(words []string) (ans int) {
n := len(words)
mask := make([]int, n)
for i, s := range words {
for _, c := range s {
mask[i] |= 1 << (c - 'a')
}
for j, t := range words[:i] {
if mask[i]&mask[j] == 0 {
ans = max(ans, len(s)*len(t))
}
}
}
return
}Approach 4: Default Approach
function maxProduct(words: string[]): number {
const mask: Map<number, number> = new Map();
let ans = 0;
for (const s of words) {
const a = s.length;
let x = 0;
for (const c of s) {
x |= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0));
}
for (const [y, b] of mask.entries()) {
if ((x & y) === 0) {
ans = Math.max(ans, a * b);
}
}
mask.set(x, Math.max(mask.get(x) || 0, a));
}
return ans;
}func maxProduct(words []string) (ans int) {
mask := map[int]int{}
for _, s := range words {
a := len(s)
x := 0
for _, c := range s {
x |= 1 << (c - 'a')
}
for y, b := range mask {
if x&y == 0 {
ans = max(ans, a*b)
}
}
mask[x] = max(mask[x], a)
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Bitmask for Character Representation | Time Complexity: O(N^2 + L) |
| Nested Loop with Set Comparison | Time Complexity: O(N^2 * L) where L is the average length of the words. |
| Bit Manipulation | – |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Nested Loop with Set Comparison | O(n^2 * L) | O(L) | Simple baseline solution when optimizing character comparison is not required |
| Bitmask for Character Representation | O(n^2) | O(n) | Best general solution; converts character checks into constant-time bit operations |
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.