Problem 318. Maximum Product of Word Lengths [Medium] - Intro to Bitmasking

Description

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.

Initial Attempt

My initial attempts were at trying to see if there was a technique I knew which could solve it but none I was familiar with applied. So I went with a brute force approach where for each word you compare it to every other word to see if they common characters.

def have_common_characters(s1, s2):
    return bool(set(s1) & set(s2))

Then, if the output is False compute the product of the lengths of s1 and s2 if it’s the largest so far then update and iterate over all pairs of strings to return the largest. This is ugly and I knew there would be some trick and better way to do it so I didn’t even bother finishing the code. Time complexity would O(n²*L) where L is the average length of words. Instead, I had a sneak peek at the optimal solution and saw what technique it used: Bitmasking.

Bitmasking

Bitmasking is a technique that uses binary numbers (bit-level operations) to efficiently represent sets, states, or flags — especially when elements come from a small finite set (like the 26 lowercase letters in our problem). Essentially how it applies to this problem: represent each word as a 26-bit integer which represent the alphabet in order. Each lowercase letter is represented by a bit in a 26-bit integer, where:

• 'a' is bit 0

• 'b' is bit 1

• 'c' is bit 2

• …

• 'z' is bit 25

This cuts down on time complexity because comparing two integers using this bitmasking technique occurs in O(1) time per pair whilst per pair the brute force technique from before was O(L).

So how do we generate these masks?

mask = 0 
for char in word: 
    mask |= (1 << (ord(char) - ord('a')))

• ord(char) - ord('a') converts every letter in the word to an index from 0 to 25 using unicode

• 1 << index bit shift: Moves the 1 left by index positions

• mask |= ... this is a bitwise assignment, updating the mask by turning on a bit at the specified position

Once all the masks are created, the rest is actually the same as the brute force method.

The final solution [Time: O(n² + n*L), Space: O(n)]

def maxProduct(self, words: List[str]) -> int:
        product = 0
        n = len(words)
        masks = []
        i = 0
        j = 0
        # Step 1: generate the masks
        while i < n:
            mask = 0
            for char in words[i]:
                mask |= (1 << (ord(char) - ord('a')))
            masks.append(mask)
            i += 1
        # Step 2: compare masks and find largest product
        for j in range(len(masks)):
            k = 0
            while k < n:
                if masks[i] & masks[j] == 0:
                    product = max(product, len(words[i]) * len(words[j]))
                k += 1
        return product

Complexity

For time complexity, step 1 is O(n*L) as each word has to be iterated over once. L is the average length of the words. Step 2 is O(n²) due to the nested loop. These two processes contribute to a total time complexity of O(n² + n*L).

Space complexity is due to the masks list which stores one integer (bitmask) per word, therefore O(n).

C++

int maxProduct(vector<string>& words) {
        int n = words.size();
        vector<int> masks(n, 0);

        // Step 1: generate the masks
        for (int i = 0; i < n; ++i) {
            for (char c : words[i]) {
                masks[i] |= (1 << (c - 'a'));
            }
        }

        // STep 2: compare masks and find largest product
        int maxProduct = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if ((masks[i] & masks[j]) == 0) {
                    int product = words[i].length() * words[j].length();
                    maxProduct = max(maxProduct, product);
                }
            }
        }

        return maxProduct;
    }