# 318. Maximum Product of Word Lengths
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:
Input: ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".
Example 2:
Input: ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words can be "ab", "cd".
Example 3:
Input: ["a","aa","aaa","aaaa"]
Output: 0
Explanation: No such pair of words.
# Solution
Approach 1: Bit manipulation.
# Code (Python)
Approach 1:
# Code (C++)
Approach 1:
class Solution {
public:
int maxProduct(vector<string>& words) {
int n = words.size();
vector<int> letters(n, 0);
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < words[i].size(); ++j)
{
letters[i] |= (1 << (words[i][j] - 'a'));
}
}
int maxLen = 0;
for (int i = 0; i < n; ++i)
{
for (int j = i + 1; j < n; ++j)
{
if ((letters[i] & letters[j]) == 0)
{
int product = words[i].size() * words[j].size();
maxLen = std::max(maxLen, product);
}
}
}
return maxLen;
}
};