Maximum Product of Word Lengths

Problem Statement

Given an array of strings named words, the task is to find the maximum product of the lengths of any two distinct words which do not share any common letters. Specifically, we are looking for the pair word[i] and word[j] where no letter in word[i] appears in word[j]. If no such pair exists, the function should return 0. This problem tests our ability to handle string manipulations and optimizations especially when the input size and possibilities are large.

Examples

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

Approach and Intuition

From the examples and constraints provided, one clear approach emerges, revolving around the effective checking of common letters between any two words and calculating their product if no common letters are found. Here's a step-by-step breakdown of an intuitive approach:

1. Convert each word into a bit mask representation:

   • Each word can be translated into a bit mask (binary representation), where each bit represents the presence (or absence) of a letter from 'a' to 'z'. This allows O(1) time complexity checks for common letters between any two words.

2. Calculate the masks:

   • Iterate over each word and calculate its mask. A dictionary or array can be used to store these masks corresponding to the words.

3. Check for common letters using masks:

   • Using the bit masks, we can determine if two words have common letters by performing a bitwise AND operation between their respective masks. If result of this operation is zero, it means the two words have no common letters.

4. Calculate and track the maximum product:

   • If two words have no common letters, compute the product of their lengths. Keep track of the maximum product found during these checks.

Given the constraints with a maximum of 1000 words, each up to 1000 characters long, this bit manipulation approach offers a significant optimization over a naïve double loop check, which would be computationally expensive and inefficient. Using bit masks not only simplifies the check for common letters but also speeds it up, making the solution feasible for larger inputs.

Solutions

class Solution {
  public int characterToIndex(char character) {
    return (int)character - (int)'a';
  }

  public int maxWordProduct(String[] words) {
    Map<Integer, Integer> map = new HashMap<>();

    int bitMask = 0;
    for (String word : words) {
      bitMask = 0;
      for (char letter : word.toCharArray()) {
        bitMask |= 1 << characterToIndex(letter);
      }
      map.put(bitMask, Math.max(map.getOrDefault(bitMask, 0), word.length()));
    }

    int result = 0;
    for (int key1 : map.keySet())
      for (int key2 : map.keySet())
        if ((key1 & key2) == 0) result = Math.max(result, map.get(key1) * map.get(key2));

    return result;
  }
}