题目描述

给定一个字符串数组words，请找到最大的length(word[i]) * length(word[j])，满足这两个单词不包含相同字母。
所有单词均只包含小写字母，如果不存在这样的两个单词，则返回0。

样例1

输入：["abcw","baz","foo","bar","xtfn","abcdef"]
输出：16 
解释：这两个单词分别是 "abcw" 和 "xtfn"。

样例2

输入：["a","ab","abc","d","cd","bcd","abcd"]
输出：4 
解释：这两个单词分别是 "ab", "cd"。

样例3

输入：["a","aa","aaa","aaaa"]
输出：0 
解释：不存在两个单词不包含相同字母。

算法

(位运算) $max(O(nL), O(n^2))$

首先我们预处理出每个单词所包含的字母集合，该集合用一个int型变量表示，如果包含第 $i$ 个小写字母，则将整型变量的第 $i$ 个二进制位置成1。

然后用两重循环枚举所有单词对，用位运算判断两个单词是否含有相同字母。假设两个单词的字母结集合别是 $state_1$ 和 $state_2$，则如果 $state_1 \& state_2 = 0$，说明不存在任何一位，两个整数都是1，也就是两个单词不包含相同字母。

时间复杂度分析：假设单词总共有 $n$ 个。初始化每个单词的字母集合的计算量是 $26n + nL$，其中 $L$ 是单词的平均长度，枚举所有单词对的计算量是 $n^2$，所以总时间复杂度是 $max(O(nL), O(n^2))$。

C++ 代码

class Solution {
public:
    int maxProduct(vector<string>& words) {
        vector<pair<int, int>> states;
        for (auto word : words)
        {
            unordered_set<char> S;
            for (auto c : word) S.insert(c);
            int state = 0;
            for (int i = 0; i < 26; i ++ )
                if (S.count(i + 'a'))
                    state += 1 << i;
            states.push_back(make_pair(state, word.size()));
        }
        int res = 0;
        for (int i = 0; i < states.size(); i ++ )
            for (int j = 0; j < i; j ++ )
            {
                if (states[i].first & states[j].first) continue;
                res = max(res, states[i].second * states[j].second);
            }
        return res;
    }
};