318. Maximum Product of Word Lengths

Description

The task is to find the maximum product of the lengths of two words in a given list, such that the two words do not share any common letters. Each word contains only lowercase English letters.

Intuition

To efficiently solve the problem, we can represent each word using a bitmask where each bit indicates whether a particular letter ('a' to 'z') is present in the word. This representation allows for fast comparison of whether two words have any common letters by using bitwise operations. By comparing the bitmasks of two words, we can quickly determine if they share common letters without manually checking each character.

Approach

1. Bitmask Representation: - Convert each word into a bitmask where the presence of each letter is represented by setting a corresponding bit in the integer. For example, the word "abc" would be represented by setting the first three bits to 1 (i.e., 000...0111).
2. Sorting: - Sort the words by length in descending order. This helps prioritize longer words early on, increasing the likelihood of finding a larger product.
3. Two-Word Comparison: - For each word, compare it with all previous words. If the bitmasks of the two words have no bits in common (i.e., their bitwise AND is zero), calculate the product of their lengths and update the maximum product found.
4. Optimization: - As soon as the product of the current word length and the longest word is smaller than the current best product, exit early from the loop to save unnecessary comparisons.

Complexity

Time Complexity:

• The time complexity is (O(n^2)) where (n) is the number of words in the list. For each word, you compare it with every other word using bitwise operations. Sorting the words takes (O(n \log n)), which is less than the quadratic comparison.

Space Complexity:

• The space complexity is (O(n)), where (n) is the number of words. This is due to the storage required for the bitmasks for each word and auxiliary data structures.

Code

C++

class Solution {
public:
    int maxProduct(vector& words) {

        sort(words.begin(), words.end(), [](const string& a, const string& b) {
            return b.length() < a.length();
        });
        int best = 0;
        vector bitsets(words.size(), 0);

        for (int i = 0; i < words.size(); i++) {
            int bitset = 0;
            int wlen = words[i].length();

            if (wlen * words[0].length() < best)
                return best;

            for (char c : words[i]) {
                bitset |= (1 << (c - 'a'));
            }
            for (int j = 0; j < i; j++) {
                if ((bitsets[j] & bitset) == 0) {
                    best = max(best, wlen * int(words[j].length()));
                }
            }
            bitsets[i] = bitset;
        }
        return best;
    }
};

Python

class Solution:
    def maxProduct(self, words: list[str]) -> int:
        words.sort(key=lambda x: len(x), reverse=True)
        best = 0
        bitsets = [0] * len(words)

        for i in range(len(words)):
            bitset = 0
            wlen = len(words[i])

            if wlen * len(words[0]) < best:
                return best

            for char in words[i]:
                bitset |= (1 << (ord(char) - ord('a')))

            for j in range(i):
                if (bitsets[j] & bitset) == 0:
                    best = max(best, wlen * len(words[j]))

            bitsets[i] = bitset

        return best

Java

class Solution {
    public int maxProduct(String[] words) {
        Arrays.sort(words, (a, b) -> b.length() - a.length());

        int best = 0;
        int[] bitsets = new int[words.length];

        for (int i = 0; i < words.length; i++) {
            int bitset = 0;
            int wlen = words[i].length();

            if (wlen * words[0].length() < best)
                return best;

            for (char c : words[i].toCharArray()) {
                bitset |= (1 << (c - '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;
    }
}

JavaScript

/**
 * @param {string[]} words
 * @return {number}
 */
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
};