# Maximum Product of Word Lengths
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-product-of-word-lengths)
Canonical: https://scaleengineer.com/dsa/problems/maximum-product-of-word-lengths
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array, String
---
## 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 <= 1000`
* `1 <= words[i].length <= 1000`
* `words[i]` consists only of lowercase English letters.

# Approaches
## Brute Force with HashSet
The most straightforward approach is to compare every pair of words and check if they share any common letters using HashSets.
**Time:** O(n² × m) where n is the number of words and m is the average length of words. We need to compare all pairs of words (n²) and for each pair, we need to check characters (m). · **Space:** O(m) where m is the length of the longest word, used for storing characters in HashSets.
**Pros:** Easy to understand and implement; No preprocessing required; Works well for small inputs
**Cons:** Creates new HashSets for each comparison; Redundant character set creation for the same words; Not efficient for large inputs
### Explanation
For each pair of words, we create HashSets containing the characters of each word. Then we check if there's any intersection between the two sets. If there's no common character, we calculate the product of their lengths and update the maximum product.

```java
public int maxProduct(String[] words) {
    int maxProduct = 0;
    
    for (int i = 0; i < words.length; i++) {
        Set<Character> set1 = new HashSet<>();
        for (char c : words[i].toCharArray()) {
            set1.add(c);
        }
        
        for (int j = i + 1; j < words.length; j++) {
            Set<Character> set2 = new HashSet<>();
            for (char c : words[j].toCharArray()) {
                set2.add(c);
            }
            
            // Check if there's any common character
            boolean hasCommon = false;
            for (char c : set1) {
                if (set2.contains(c)) {
                    hasCommon = true;
                    break;
                }
            }
            
            if (!hasCommon) {
                maxProduct = Math.max(maxProduct, words[i].length() * words[j].length());
            }
        }
    }
    
    return maxProduct;
}
```
### Algorithm
1. Iterate through all pairs of words (i, j) where i < j
2. For each word in the pair, create a HashSet of its characters
3. Check if the two HashSets have any common characters
4. If no common characters exist, calculate the product of lengths
5. Keep track of the maximum product found
6. Return the maximum product

## Precomputed HashSets
Optimize the brute force approach by precomputing the character sets for all words once, avoiding redundant set creation.
**Time:** O(n × m + n²) where n is the number of words and m is the average length. Preprocessing takes O(n × m) and comparisons take O(n²). · **Space:** O(n × 26) = O(n) for storing character sets for all words (at most 26 characters per set).
**Pros:** Avoids redundant HashSet creation; More efficient than the basic brute force; Still easy to understand
**Cons:** Still requires checking all pairs; HashSet operations have some overhead; Not the most space-efficient representation
### Explanation
Instead of creating HashSets repeatedly for each comparison, we precompute all character sets once at the beginning. This reduces the overhead of creating sets multiple times for the same words.

```java
public int maxProduct(String[] words) {
    int n = words.length;
    Set<Character>[] charSets = new Set[n];
    
    // Precompute character sets for all words
    for (int i = 0; i < n; i++) {
        charSets[i] = new HashSet<>();
        for (char c : words[i].toCharArray()) {
            charSets[i].add(c);
        }
    }
    
    int maxProduct = 0;
    
    // Compare all pairs of words
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // Check if words share any common character
            boolean hasCommon = false;
            for (char c : charSets[i]) {
                if (charSets[j].contains(c)) {
                    hasCommon = true;
                    break;
                }
            }
            
            if (!hasCommon) {
                maxProduct = Math.max(maxProduct, words[i].length() * words[j].length());
            }
        }
    }
    
    return maxProduct;
}
```
### Algorithm
1. Create an array to store HashSets for each word
2. Precompute character sets for all words
3. Compare all pairs of words using the precomputed sets
4. For each pair, check if they share any common characters
5. If no common characters, update the maximum product
6. Return the maximum product

## Bit Manipulation
Use bit manipulation to represent each word as a bitmask where each bit represents the presence of a character, enabling efficient comparison using bitwise AND operation.
**Time:** O(n × m + n²) where n is the number of words and m is the average length. Creating bitmasks takes O(n × m) and comparing all pairs takes O(n²). · **Space:** O(n) for storing the bitmask array.
**Pros:** Very efficient character comparison using single bitwise operation; Compact representation of character sets; No need for HashSet operations; Optimal solution for this problem
**Cons:** Limited to problems with small character sets (26 letters fit in an integer); Requires understanding of bit manipulation; Still needs to check all pairs of words
### Explanation
Since we only have lowercase English letters (26 total), we can use an integer where each bit represents whether a specific character exists in the word. Two words share no common letters if and only if the bitwise AND of their bitmasks is 0.

```java
public int maxProduct(String[] words) {
    int n = words.length;
    int[] bitmasks = new int[n];
    
    // Convert each word to a bitmask
    for (int i = 0; i < n; i++) {
        for (char c : words[i].toCharArray()) {
            bitmasks[i] |= 1 << (c - 'a');
        }
    }
    
    int maxProduct = 0;
    
    // Compare all pairs using bitwise AND
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if ((bitmasks[i] & bitmasks[j]) == 0) {
                maxProduct = Math.max(maxProduct, words[i].length() * words[j].length());
            }
        }
    }
    
    return maxProduct;
}
```

The bit manipulation works as follows:
- For character 'a', we set bit 0: `1 << 0 = 1`
- For character 'b', we set bit 1: `1 << 1 = 2`
- For character 'z', we set bit 25: `1 << 25`

Example: "abc" → bitmask = 0...0111 (bits 0, 1, 2 are set)
### Algorithm
1. Create an array to store bitmasks for each word
2. For each word, create a bitmask by setting bits corresponding to characters
3. Compare all pairs of words using bitwise AND operation
4. If (bitmask1 & bitmask2) == 0, the words share no common characters
5. Update maximum product for valid pairs
6. Return the maximum product

# Solutions
### Java

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

### CPP

```cpp
class Solution { public: int maxProduct ( vector < string >& words ) { int n = words . size (); int mask [ n ]; memset ( mask , 0 , sizeof ( mask )); int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { for ( char & c : words [ i ]) { mask [ i ] |= 1 << ( c - 'a' ); } for ( int j = 0 ; j < i ; ++ j ) { if (( mask [ i ] & mask [ j ]) == 0 ) { ans = max ( ans , ( int ) ( words [ i ]. size () * words [ j ]. size ())); } } } return ans ; } };
```

### Python

```python
class Solution : def maxProduct ( self , words : List [ str ]) -> int : n = len ( words ) mask = [ 0 ] * n for i , word in enumerate ( words ): for ch in word : mask [ i ] |= 1 << ( ord ( ch ) - ord ( 'a' )) ans = 0 for i in range ( n - 1 ): for j in range ( i + 1 , n ): if mask [ i ] & mask [ j ] == 0 : ans = max ( ans , len ( words [ i ]) * len ( words [ j ])) return ans ############ class Solution ( object ): def maxProduct ( self , words ): """ :type words: List[str] :rtype: int """ bitmap = [ 0 ] * len ( words ) mask = 0x01 ans = 0 for i in range ( 0 , len ( words )): word = words [ i ] for c in word : bitmap [ i ] |= ( mask << ( ord ( c ) - ord ( 'a' ))) for i in range ( 0 , len ( words )): for j in range ( 0 , i ): if bitmap [ i ] & bitmap [ j ] == 0 : ans = max ( ans , len ( words [ i ]) * len ( words [ j ])) return ans
```