318. Maximum Product of Word Lengths

• Difficulty: Medium

• Topics: Bit Manipulation

• Similar Questions:

Problem:

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.

Solutions:

class Solution {
public:
    int maxProduct(vector<string>& words) {
        unordered_map<int, int> indexToBit;

        for (int i = 0; i < words.size(); ++i) {
            int bitmap = getBitMap(words[i]);
            indexToBit[i] = bitmap;
        }

        int ret = 0;
        for (int i = 0; i < words.size(); ++i) {
            for (int j = i + 1; j < words.size(); ++j) {
                if ((indexToBit[i] & indexToBit[j]) == 0) {
                    ret = max(ret, (int) (words[i].length() * words[j].length()));
                }
            }
        }

        return ret;
    }

private:
    int getBitMap(const string& word) {
        int bitmap = 0;
        for (auto& c : word) {
            bitmap |= 1 << (c - 'a');
        }

        return bitmap;
    }

};