318. Maximum Product of Word Lengths

Given a string arraywords, find the maximum value oflength(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:

Given["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return16
The two words can be"abcw", "xtfn".

Example 2:

Given["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return4
The two words can be"ab", "cd".

Example 3:

Given["a", "aa", "aaa", "aaaa"]
Return0
No such pair of words.

S：bit manipulation O(n^2)

可以用26个bit表示每个字符出现的情况，因为只有26个字母，可用一个int表示。这样只用进行&操作就可以判断两string是否有相同的字符

    int maxProduct(vector<string>& words) {
        int n = words.size();
        int result = 0;
        vector<int> letter(n, 0);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < words[i].size(); ++j) {
                letter[i] |= (1 << (words[i][j] - 'a')); 
            }
            for (int j = 0; j < i; ++j) {
                if (!(letter[i] & letter[j])) {
                    result = max(result, (int)(words[i].size() * words[j].size()));
                }
            }
        }
        return result;
    }