Leetcode 318. Maximum Product of Word Lengths

Problem Explanation

We are given an array of words, and the task is to calculate the maximum value of the product of lengths of two words such that there is no common letter in the two words. Each word provided will only consist of lowercase alphabets. If there are no such pairs, return 0.

For example, consider ["abc","dee","cdf"]. The maximum product of word lengths comes from the pair "abc" and "dee" because both words do not share a common alphabet - they are completely different alphabets. Thus, the result would be 3 (length of "abc") * 3 (length of "dee") = 9.

Solution Approach

This problem can be solved by generating a mask for every word, where each bit of the mask represents existence of the alphabet (a-z) in that word. Then, for each pair of words with no common alphabets, (masks[i] & masks[j]) == 0 will be true. For those pairs, calculate word length product and update max length product if current one is bigger.

Finally, the max length product is returned.

To visualize this let's take ["abc", "xo", "die"]. The masks for the words will be [1, 2, 3] - 1 for "abc" meaning these alphabets exist in the word, 2 for "xo", and 3 for "die". Comparing two masks with bitwise '&', for example, 1 & 2 == 0 (binary comparison of 0001 and 0010), indicating there are no common alphabets. So, this pair can be used to calculate word length product which is length("abc") * length("xo") = 3 * 2 = 6.

The algorithm uses bitwise operations and dynamic programming concept. Let's dive into the solution code.

H2 Python Solution

1
2python
3class Solution:
4    def maxProduct(self, words: List[str]) -> int:
5        masks = [0]*len(words)
6        lengths = [0]*len(words)
7
8        for i in range(len(words)):
9            word = words[i]
10            for w in word:
11                # create a unique mask for each word
12                masks[i] |= 1 << (ord(w) - 97)  
13            lengths[i] = len(word)
14        
15        maxProduct = 0
16        for i in range(len(masks)):
17            for j in range(i):
18                if masks[i] & masks[j] == 0:   # no common character
19                    maxProduct = max(maxProduct, lengths[i]*lengths[j]) # max product
20        return maxProduct

H2 Java Solution

1
2java
3class Solution {
4    public int maxProduct(String[] words) {
5        int[] masks = new int[words.length];
6        int[] lengths = new int[words.length];
7        int maxProduct = 0;
8        
9        for (int i = 0; i < words.length; ++i) {
10            for (char c : words[i].toCharArray()) {
11                masks[i] |= 1 << (c - 'a');  
12            }
13            lengths[i] = words[i].length();
14        }
15        
16        for (int i = 0; i < masks.length; ++i) {
17            for (int j = 0; j < i; ++j) {
18                if ((masks[i] & masks[j]) == 0) {
19                    maxProduct = Math.max(maxProduct, lengths[i] * lengths[j]);
20                }
21            }
22        }
23        return maxProduct;
24    }
25}

H2 JavaScript Solution

1
2javascript
3var maxProduct = function(words) {
4    let masks = [];
5    let lengths = []
6    let maxProduct= 0;
7    
8    for (let i = 0; i < words.length; ++i) {
9        for (let c of words[i]) {
10            masks[i] |= 1 << (c.charCodeAt(0) - 97);  
11        }
12        lengths[i] = words[i].length;
13    }
14    
15    for (let i = 0; i < masks.length; ++i) {
16        for (let j = 0; j < i; ++j) {
17            if ((masks[i] & masks[j]) === 0) {
18                maxProduct = Math.max(maxProduct, lengths[i] * lengths[j]);
19            }
20        }
21    }
22    return maxProduct;
23};

H2 C++ Solution

1
2C++
3class Solution {
4public:
5    int maxProduct(vector<string>& words) {
6        vector<int> masks(words.size());
7        vector<int> lengths(words.size());
8        int maxProduct = 0;
9
10        for (int i = 0; i < words.size(); ++i) {
11            for (char c : words[i]) {
12                masks[i] |= 1 << (c - 'a');
13            }
14            lengths[i] = words[i].length();
15        }
16
17        for (int i = 0; i < masks.size(); ++i) {
18            for (int j = 0; j < i; ++j) {
19                if (!(masks[i] & masks[j])) {
20                    maxProduct = max(maxProduct, lengths[i] * lengths[j]);
21                }
22            }
23        }
24
25        return maxProduct;
26    }
27};

H2 C# Solution

1
2csharp
3public class Solution {
4    public int MaxProduct(string[] words) {
5        int[] masks = new int[words.Length];
6        int[] lengths = new int[words.Length];
7        int maxProduct = 0;
8        
9        for (int i = 0; i < words.Length; ++i) {
10            foreach (char c in words[i]){
11                masks[i] |= 1 << (c - 'a');
12            }
13            lengths[i] = words[i].Length;
14        }
15        
16        for (int i = 0; i < masks.Length; ++i) {
17            for (int j = 0; j < i; ++j) {
18               if ((masks[i] & masks[j]) == 0) {
19                    maxProduct = Math.Max(maxProduct, lengths[i] * lengths[j]);
20                }
21            }
22        }
23        return maxProduct;
24    }
25}

In these solutions, each word is converted into a bitmask, where the bit at position n is set if the word contains the nth letter of the alphabet. By comparing two bitmasks with the bitwise AND operation (&), we can confirm whether two words have common letters or not.

In python, the ord() function gives us the ASCII value of a character, so ord(w) - 97 gives the position of the letter in the alphabet.

In Java, the same process is done by subtracting 'a' from the character.

In JavaScript, the charCodeAt() function is used in case of the absence of direct character to ASCII conversion. As in other solutions, the ASCII code of 'a' (97) is subtracted to get the position in the alphabet.

Similarly, in C++ and C#, the word string is iterated through character by character where it gets masked with bitwise shift to the left by (c - 'a') points.

Next, all possible pairs are iterated through. If the words in a pair have no common characters, then the maximum product of lengths is updated with the product of the lengths of these two words, if it's larger.

At the end, the function returns the maximum product. Note that if there are no two words without common characters, the result will be 0 (which is the initial value of maxProduct).

These solutions have a time complexity of O(N^2+M) (N being the number of words and M being the total number of characters in all words), because to generate masks we have to iterate over all characters in all words, and then to find the pair with the maximum product we have to iterate over all possible pairs of words which give a quadratic time complexity. The space complexity of the solution is O(N) because we use two extra arrays of size N.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫