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.

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;
}