## Algorithm

Problem Name: 318. Maximum Product of Word Lengths

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`.

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.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int maxProduct(char** words, int wordsSize) {
char *s;
int *b, *l; // bits and length
int i, j;
int x, k = 0;

if (wordsSize < 2) return 0;

b = calloc(wordsSize * 2, sizeof(int));
//assert(b);

l = &b[wordsSize];

i = 0;
while (i < wordsSize) {
s = words[i];
while (s && *s) {
b[i] |= 1 << (*s - 'a');
l[i] ++;
s ++;
}
​
j = 0;
while (j < i) {
if ((b[j] & b[i]) == 0) {
x = l[j] * l[i];
if (k < x) k = x;
}
j ++;
}
i ++;
}

free(b);

return k;
}
``````
Copy The Code &

Input

cmd
words = ["abcw","baz","foo","bar","xtfn","abcdef"]

Output

cmd
16

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int maxProduct(vector& words) {
int maxlen = 0;
for(int i = 0; i < words.size(); i++)
for(int j = i + 1; j < words.size(); j++){
if(words[i].size() * words[j].size() <= maxlen) continue;
if(noCommon(words[i], words[j])) maxlen = max(maxlen, (int)(words[i].size() * words[j].size()));
}
return maxlen;
}

bool noCommon(string& a, string& b){
for(auto x: a)
for(auto y: b)
if(x == y) return false;
return true;
}
};
``````
Copy The Code &

Input

cmd
words = ["abcw","baz","foo","bar","xtfn","abcdef"]

Output

cmd
16

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int maxProduct(String[] words) {
int maxProd = 0;
for (int i = 0; i < words.length; i++) {
for (int j = i + 1; j < words.length; j++) {
if (noCommonLetters(words[i], words[j])) {
maxProd = Math.max(maxProd, words[i].length() * words[j].length());
}
}
}
return maxProd;
}

private boolean noCommonLetters(String s1, String s2) {
for (char c : s1.toCharArray()) {
bitMaskOne |= 1 << ((int) c - (int) 'a');
}
for (char c : s2.toCharArray()) {
bitMaskTwo |= 1 << ((int) c - (int) 'a');
}
}
}
``````
Copy The Code &

Input

cmd
words = ["a","ab","abc","d","cd","bcd","abcd"]

Output

cmd
4

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const maxProduct = function(words) {
if (words == null || words.length === 0) return 0;
let len = words.length;
let value = [];
for (let i = 0; i < len; i++) {
let tmp = words[i];
value[i] = 0;
for (let j = 0; j < tmp.length; j++) {
value[i] |= 1 << (tmp.charAt(j).charCodeAt(0) - "a".charCodeAt(0));
}
}
let maxProductNum = 0;
for (let i = 0; i < len; i++)
for (let j = i + 1; j < len; j++) {
if (
(value[i] & value[j]) === 0 &&
words[i].length * words[j].length > maxProductNum
)
maxProductNum = words[i].length * words[j].length;
}
return maxProductNum;
};
``````
Copy The Code &

Input

cmd
words = ["a","ab","abc","d","cd","bcd","abcd"]

Output

cmd
4

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def maxProduct(self, words):
sets, mx = {w: set(w) for w in words}, 0
words.sort(key = len, reverse = True)
for i in range(len(words) - 1):
for j in range(i + 1, len(words)):
if len(words[i]) * len(words[j]) <= mx:
break
elif not sets[words[i]] & sets[words[j]]:
mx = len(words[i]) * len(words[j])
return mx
``````
Copy The Code &

Input

cmd
words = ["a","aa","aaa","aaaa"]