Description:

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.

Link:

https://leetcode.com/problems/maximum-product-of-word-lengths/description/

解题方法：

假设我们有n个单词，总共有N个字符。
因为没有找到一种方法可以使有相同字母的单词共享一个key的方法，所以这道题是O(n^2)级别的算法。
因为int有32位，如果把26个字母转化为int上每一个位的0或1。我们可以用根据出现字母的组合来定义一个key并且用int储存这个组合。

Tips:

string::size()返回的是size_type类型的值，所以在使用Max函数的时候要注意转换为int。

Time Complexity：

O(max(N, n^2))

完整代码：

int maxProduct(vector<string>& words) 
    { 
        unordered_map<int, int> hash;
        for(string str: words)
        {
            int mask = 0;
            for(char ch: str)
            {
                mask |= (1 << (ch - 'a'));
            }
            hash[mask] = max(hash[mask], (int)str.size());   //different words may have same mask, so we need to save the max value
        }
        int maxPrud = 0;
        for(auto a: hash)
        {
            for(auto b: hash)
            {
                if(!(a.first & b.first))    //a and b have different masks, which means a and b don't share common letter
                    maxPrud = max(a.second * b.second, maxPrud);
            }
        }
        return maxPrud;
    }