# Maximum Product of Word Lengths (Leetcode 318)

Difficulty: Medium Link: Day 27: May Leetcode Challenge

## Problem Statement

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

``````Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".
``````
``````Input: words = ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words can be "ab", "cd".
``````
``````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.

## Solution

The important thing to note here is that letters should not be common among the two strings but can be duplicate in itself. This is important if you decide to use sets to check if they have letters in common. Since sets reduces to unique values the set count of combined string would be less than individual set counts. However since letters can be duplicate inside the string so set will reduce them as well.

We can try the solution and checking pairwise for every string if they have no common letters and saving the max length. However, this is already a O(N2) operation and if we are performance O(L) operations on strings then complexity would shoot upwards of O(N2). We need a strategy to precompute the results and then only check pair-wise which will keep our solution under O(N2).

### Bitmasking

Since letters are only given as lowercase english letters, the number of different alphabets can be only 26. We can use a bit-mask of 26 digits to mask the occurrence the any letter. Bitmasks can help us to determine if two strings share a common letter in O(1) which is a significant optimisation from O(L1 + L2). We can simple apply ‘&’ operator on two bitmasks and if result is 0 then there is no common letter. Bitwise AND would be zero if all bits are difference hence no letter map to the same bit offset.

To save the results, we can cache them in a dictionary mapping bit-mask to its length. Also note, that multiple words can have same bitmasks (“ab”, “aaab”, “abbbb”). So we only need to keep the word with the longest length for optimal result. Bit masking words

## Complexity Analysis

In the worst case, bit mask of every value would be unique and we would be to check pair-wise which would be O(N2). We are also iterating through every word for bit mask value conversion and in case N is small but string lengths are very big (L > N2), then complexity would be bounded by the total length of all strings L.

Time = O(N2 + L) // Where N is number of strings and L is total count of lengths.

Space = O(N) // Every Bitmask needs to be stored.