Maximum Product of Word Lengths

medium array string bit manipulation

Problem

Given an array of strings, return the maximum value of length(words[i]) · length(words[j]) where the two words do not share any letters. If no such pair exists, return 0.

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

Output16

"abcw" × "xtfn" → 4 × 4 = 16.

words (comma-separated)

def max_product(words):
    n = len(words)
    masks = [0] * n
    for i, w in enumerate(words):
        for ch in w:
            masks[i] |= 1 << (ord(ch) - ord('a'))
    best = 0
    for i in range(n):
        for j in range(i + 1, n):
            if masks[i] & masks[j] == 0:
                best = max(best, len(words[i]) * len(words[j]))
    return best

function maxProduct(words) {
  const n = words.length;
  const masks = new Array(n).fill(0);
  for (let i = 0; i < n; i++)
    for (const ch of words[i])
      masks[i] |= 1 << (ch.charCodeAt(0) - 97);
  let best = 0;
  for (let i = 0; i < n; i++)
    for (let j = i + 1; j < n; j++)
      if ((masks[i] & masks[j]) === 0)
        best = Math.max(best, words[i].length * words[j].length);
  return best;
}

class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        int[] masks = new int[n];
        for (int i = 0; i < n; i++)
            for (char c : words[i].toCharArray())
                masks[i] |= 1 << (c - 'a');
        int best = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if ((masks[i] & masks[j]) == 0)
                    best = Math.max(best, words[i].length() * words[j].length());
        return best;
    }
}

int maxProduct(vector<string>& words) {
    int n = words.size();
    vector<int> masks(n, 0);
    for (int i = 0; i < n; i++)
        for (char c : words[i])
            masks[i] |= 1 << (c - 'a');
    int best = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if ((masks[i] & masks[j]) == 0)
                best = max(best, (int)words[i].size() * (int)words[j].size());
    return best;
}

Explanation

We want the biggest product of two word lengths where the two words share no letters. Checking letter overlap directly is slow, so we encode each word's letter set as a 26-bit bitmask and compare masks instead.

For each word, we set bit c - 'a' for every letter it contains. Two words have no common letter exactly when masks[i] & masks[j] == 0 — their bit sets do not overlap anywhere.

After building all masks, we try every pair (i, j). Whenever their AND is zero, the words are disjoint, so we compute len(words[i]) * len(words[j]) and keep the largest product seen in best.

Example: words = ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]. The masks for "abcw" and "xtfn" share no bits, so they qualify, giving 4 * 4 = 16, which is the maximum.

The clever part is that the overlap test is a single AND on integers, so the pair loop runs fast even though we compare every pair.

Time: O(n² + Σ|w|) Space: O(n)