## DEV Community is a community of 668,514 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Solution: Maximum Product of Word Lengths

seanpgallivan
Fledgling software developer; the struggle is a Rational Approximation.

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

#### Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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`.

#### 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.

#### Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

The obvious first concern of this problem is evaluating if two words contain the same letters. This naturally calls for making a character set of each word, but comparing these sets is still not easy.

If we use bit manipulation, however, to create character bitsets, then it should be easy enough to use a bitwise AND (&) to compare the two bitset integers where any result other than 0 means overlapping characters.

This solution still calls for a time complexity of at least O(N^2), since we'll have to compare each combination of words together. We can optimize this a bit more by first sorting words by descending length, which should result in finding the larger products earlier. In fact, as we iterate through the sorted words, we can isolate when it will no longer be possible for a word to produce a best result, at which point we can immediately return best.

Also, we don't need to convert each word into a bitset before we start our comparisons. As we finish converting each word into its bitset, we can compare it to all the previously completed results stored in bitsets.

After we finish comparing the current bitset, we can add it to the bitsets array for comparison with later results.

• Time Complexity: O(N^2 + N*M) where N is the length of words and M is the average length of the words in words
• Space Complexity: O(N) for bitsets

#### Implementation:

Python is oddly faster if the bitsets and word lengths are stored together as key value pairs in a dict prior to comparison.

Java and C++ sorts are slow enough to make them not an effective optimizations, at least with the given test suite.

#### Javascript Code:

``````var maxProduct = function(words) {
words.sort((a,b) => b.length - a.length)
let best = 0, bitsets = new Uint32Array(words.length)
for (let i = 0; i < words.length; i++) {
let word = words[i], wlen = word.length, bitset = 0
if (wlen * words[0].length < best)
return best
for (let j = 0; j < wlen; j++)
bitset |= 1 << (word.charCodeAt(j) - 97)
for (let j = 0; j < i; j++)
if ((bitsets[j] & bitset) === 0)
best = Math.max(best, wlen * words[j].length)
bitsets[i] = bitset
}
return best
};
``````

#### Python Code:

``````class Solution:
def maxProduct(self, words: List[str]) -> int:
words.sort(key=len, reverse=True)
best, bitsets = 0, {}
for i in range(len(words)):
wlen, bitset = len(words[i]), 0
if wlen * len(words[0]) < best:
return best
for c in words[i]:
bitset |= 1 << ord(c) - 97
if bitset not in bitsets:
for k,v in bitsets.items():
if not bitset & k:
best = max(best, wlen * v)
bitsets[bitset] = wlen
return best
``````

#### Java Code:

``````class Solution {
public int maxProduct(String[] words) {
int best = 0;
int[] bitsets = new int[words.length];
for (int i = 0; i < words.length; i++) {
int wlen = words[i].length(), bitset = 0;
for (int j = 0; j < wlen; j++)
bitset |= 1 << (words[i].charAt(j) - 'a');
for (int j = 0; j < i; j++)
if ((bitsets[j] & bitset) == 0)
best = Math.max(best, wlen * words[j].length());
bitsets[i] = bitset;
}
return best;
}
}
``````

#### C++ Code:

``````class Solution {
public:
int maxProduct(vector<string>& words) {
int best = 0;
vector<int> bitsets(words.size());
for (int i = 0; i < words.size(); i++) {
string& word = words[i];
int bitset = 0;
for (char& c : word)
bitset |= 1 << (c - 'a');
for (int j = 0; j < i; j++)
if ((bitsets[j] & bitset) == 0)
best = max(best, int(word.length() * words[j].length()));
bitsets[i] = bitset;
}
return best;
}
};
``````