Solution: Maximum Product of Word Lengths

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.

Leetcode Problem #318 (Medium): Maximum Product of Word Lengths

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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