Maximum Product of Word Lengths

MEDIUM

Description

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

Checkout 3 different approaches to solve Maximum Product of Word Lengths. Click on different approaches to view the approach and algorithm in detail.

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.

Algorithm

Iterate through all pairs of words (i, j) where i < j
For each word in the pair, create a HashSet of its characters
Check if the two HashSets have any common characters
If no common characters exist, calculate the product of lengths
Keep track of the maximum product found
Return the maximum product

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.

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;
}

Complexity Analysis

Time Complexity: 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 Complexity: O(m) where m is the length of the longest word, used for storing characters in HashSets.

Pros and Cons

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

Code Solutions

Checking out 3 solutions in different languages for Maximum Product of Word Lengths. Click on different languages to view the code.

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 ; } }

Video Solution

Watch the video walkthrough for Maximum Product of Word Lengths

Patterns:

Bit Manipulation

Data Structures:

ArrayString