Scale Engineer

Maximum Product of Word Lengths

Med
#0305Time: 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.
Patterns
Bit Manipulation
Data structures
ArrayString

Prompt

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

3 approaches with complexity analysis and trade-offs.

The most straightforward approach is to compare every pair of words and check if they share any common letters using HashSets.

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

Walkthrough

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

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.

Trade-offs

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

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem