Maximum Product of Word Lengths

Desicription

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

1
2
3
Input: ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

Example 2:

1
2
3
Input: ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words can be "ab", "cd".

Example 3:

1
2
3
Input: ["a","aa","aaa","aaaa"]
Output: 0
Explanation: No such pair of words.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int maxProduct(std::vector<std::string>& words) {
auto visits = std::vector<std::bitset<26>>(words.size(), 0);
for(int i = 0; i < words.size(); i++) {
auto word = words[i];
for(char c : word) {
visits[i][c - 'a'] = true;
}
}

int maxLength = 0;
for(int i = 0; i < words.size(); i++) {
for(int j = i + 1; j < words.size(); j++) {
if((visits[i] & visits[j]).to_ulong() == 0) {
maxLength = std::max(maxLength, (int)words[i].size() * (int)words[j].size());
}
}
}

return maxLength;
}
};