Maximum Product of Word Lengths
MedPrompt
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 <= 10001 <= words[i].length <= 1000words[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
- 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
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
Optimize the brute force approach by precomputing the character sets for all words once, avoiding redundant set creation.
Algorithm
- Create an array to store HashSets for each word
- Precompute character sets for all words
- Compare all pairs of words using the precomputed sets
- For each pair, check if they share any common characters
- If no common characters, update the maximum product
- Return the maximum product
Walkthrough
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.
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;}Complexity
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).
Trade-offs
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
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.
Algorithm
- Create an array to store bitmasks for each word
- For each word, create a bitmask by setting bits corresponding to characters
- Compare all pairs of words using bitwise AND operation
- If (bitmask1 & bitmask2) == 0, the words share no common characters
- Update maximum product for valid pairs
- Return the maximum product
Walkthrough
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.
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)
Complexity
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.
Trade-offs
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
Solutions
Solution
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 ; } }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 ; } };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 ansVideo 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.