Maximum Product of Word Lengths

Medium
428.

Maximum Product of Word Lengths

Maximum Product of Word Lengths is a medium coding problem on arrays, strings and bit manipulation, asked in Amazon, Google and Meta interviews.

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 <= 20
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @return {number}
 */
var maxProduct = function(words) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 20
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters.

Hints for Maximum Product of Word Lengths

  1. Hint 1

    Comparing letter sets directly is slow — encode each word as a 26-bit mask instead.

  2. Hint 2

    Two words share a letter exactly when the AND of their masks is non-zero.

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

  1. Build a mask per word.
  2. 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 best

Java

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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings