318. Maximum Product of Word Lengths ----M !!!!!!!!!!!!!

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.

 

Constraints:

• 0 <= words.length <= 10^3
• 0 <= words[i].length <= 10^3
• words[i] consists only of lowercase English letters.

A:
这个问题的核心就在于快速计算2个String是否有相同的char
因此，我们用一个1D数组，大小为26。  进而我们用一个int来代表。

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int n = words.size();
        vector<int> M(n,0);  // flag to map from index to 26 long bit (as int)
        for(int i =0; i<n; i++){
            for(char ch : words[i]){
                M[i] |= (1<< (ch-'a'));
            }
        }
        int res = 0;
        for(int i = 0;i< n; i++){            
            for(int j = i+1; j<n;j++){
                if( not (M[i] & M[j])){
                    res = max(res, int(words[i].length() * words[j].length()));
                }
            }
        }
        return res;
    }
};

Mistakes: