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.
int maxProduct(vector<string>& words) { // time: O(n^2); space: O(n)
int n = words.size(), res = 0;
vector<int> lengths(n), bitmasks(n);
for (int i = 0 ; i < n; ++i) lengths[i] = words[i].length();
for (int i = 0; i < n; ++i) {
for (char ch : words[i]) {
bitmasks[i] |= 1 << (ch - 'a');
}
for (int j = 0; j < i; ++j) {
if (!(bitmasks[i] & bitmasks[j])) {
res = max(res, lengths[i] * lengths[j]);
}
}
}
return res;
}