Code Implementation

class Solution:
    def maxProduct(self, words):
        n = len(words)
        bitmasks = [0] * n
        for i, word in enumerate(words):
            for ch in word:
                bitmasks[i] |= 1 << (ord(ch) - ord('a'))
        max_prod = 0
        for i in range(n):
            for j in range(i + 1, n):
                if bitmasks[i] & bitmasks[j] == 0:
                    prod = len(words[i]) * len(words[j])
                    if prod > max_prod:
                        max_prod = prod
        return max_prod
      

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int n = words.size();
        vector<int> bitmasks(n, 0);
        for (int i = 0; i < n; ++i) {
            for (char ch : words[i]) {
                bitmasks[i] |= 1 << (ch - 'a');
            }
        }
        int max_prod = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if ((bitmasks[i] & bitmasks[j]) == 0) {
                    int prod = words[i].size() * words[j].size();
                    if (prod > max_prod) max_prod = prod;
                }
            }
        }
        return max_prod;
    }
};
      

class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        int[] bitmasks = new int[n];
        for (int i = 0; i < n; ++i) {
            for (char ch : words[i].toCharArray()) {
                bitmasks[i] |= 1 << (ch - 'a');
            }
        }
        int maxProd = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if ((bitmasks[i] & bitmasks[j]) == 0) {
                    int prod = words[i].length() * words[j].length();
                    if (prod > maxProd) maxProd = prod;
                }
            }
        }
        return maxProd;
    }
}
      

var maxProduct = function(words) {
    const n = words.length;
    const bitmasks = new Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
        for (const ch of words[i]) {
            bitmasks[i] |= 1 << (ch.charCodeAt(0) - 'a'.charCodeAt(0));
        }
    }
    let maxProd = 0;
    for (let i = 0; i < n; ++i) {
        for (let j = i + 1; j < n; ++j) {
            if ((bitmasks[i] & bitmasks[j]) === 0) {
                let prod = words[i].length * words[j].length;
                if (prod > maxProd) maxProd = prod;
            }
        }
    }
    return maxProd;
};
      

Problem Description

Given a list of strings called words, your goal is to find the maximum value of length(word1) * length(word2) where word1 and word2 are two different words from the list and they do not share any common letters (i.e., every letter in word1 is different from every letter in word2). If no such pair exists, return 0.

• Each word consists only of lowercase English letters.
• Each pair must be made of two distinct words; you cannot use the same word twice.
• You may assume there is at least one valid solution, or return 0 if none exists.

Thought Process

To solve this problem, we need to consider all possible pairs of words and check if they have no common letters. If they don't, we calculate the product of their lengths and keep track of the maximum product found.

The most direct (brute-force) way is to check every pair and compare their characters one by one. However, this is inefficient, especially if there are many words or if the words are long.

To optimize, we realize that checking for common letters can be done much faster by representing each word as a bitmask (an integer where each bit represents the presence of a letter). This allows us to check for shared letters between two words using a single bitwise AND operation.

This shift from comparing individual letters to comparing bitmasks is the key insight for an efficient solution.

Solution Approach

• Step 1: Represent Each Word as a Bitmask
  • For each word, create an integer where each bit corresponds to a letter (e.g., bit 0 for 'a', bit 1 for 'b', ..., bit 25 for 'z').
  • If a letter is present in the word, set its corresponding bit to 1.
  • This allows us to quickly check if two words share any letters: if bitmask1 & bitmask2 == 0, they have no letters in common.
• Step 2: Compare All Pairs Using Bitmasks
  • For every pair of words, check their bitmasks with a bitwise AND operation.
  • If the result is zero, multiply their lengths and update the maximum product if it's the largest seen so far.
• Step 3: Return the Maximum Product
  • After checking all pairs, return the highest product found. If no such pair exists, return 0.

Using bitmasks is efficient because checking for common letters takes constant time, regardless of word length.

Example Walkthrough

Let's use the input words = ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"].

1. First, convert each word to a bitmask:
   • "abcw": bits set for a, b, c, w
   • "baz": bits set for b, a, z
   • "foo": bits set for f, o
   • "bar": bits set for b, a, r
   • "xtfn": bits set for x, t, f, n
   • "abcdef": bits set for a, b, c, d, e, f
2. Now, compare all pairs:
   • "abcw" (4 letters) and "xtfn" (4 letters): no common letters, product is 16
   • Check other pairs: "abcw" and "foo" share 'f', so skip; "abcw" and "baz" share 'a', etc.
   • The pair "abcw" and "xtfn" gives the largest product (16).
3. The function returns 16.

Time and Space Complexity

• Brute-force Approach:
  • Checking all pairs: O(N^2), where N is the number of words.
  • Checking if two words share letters: O(L), where L is the average word length.
  • Total: O(N^2 * L)
• Optimized Bitmask Approach:
  • Building bitmasks: O(N * L)
  • Checking all pairs with bitwise AND: O(N^2)
  • Total: O(N^2 + N*L)
  • Space: O(N) for bitmask array
• The optimized approach is much faster, especially for longer words.

Summary

The Maximum Product of Word Lengths problem can be solved efficiently by representing each word as a bitmask, allowing us to check for common letters using fast bitwise operations. This reduces the time spent checking each pair and makes the solution scalable even for large inputs. The key insight is to transform the problem from string comparison to bit manipulation, resulting in a clean and elegant solution.