题目描述：

给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。

示例 1：

输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出：16 
解释：这两个单词为 "abcw", "xtfn"。

示例 2：

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

示例 3：

输入：words = ["a","aa","aaa","aaaa"]
输出：0 
解释：不存在这样的两个单词。

提示：

• 2 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] 仅包含小写字母

解法一：位运算

算法思路：

我们可以使用二进制数来代表每个字符串，利用一个 32 位的整型数即可。由于每个字符串仅包含小写字母，这个二进制数的每一位表示相应位置的字母是否在字符串中出现。

若两个字符串没有共同的字母，对应的二进制数经过按位与操作的结果将为 0，即 mask[i] & mask[j] == 0。

具体来说，我们遍历每个字符串。对于当前遍历到的字符串 words[i]，我们首先计算出其对应的二进制数 mask[i]，然后遍历所有在 j ∈ [0, i) 范围内的字符串的 mask[j]。我们检查 mask[i] & mask[j] == 0 是否为真。若成立，则更新答案为 max(ans, |words[i]| × |words[j]|)。

遍历完成后，返回得到的答案即可。

代码实现：

class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        int[] mask = new int[n];
        int ans = 0;
        for(int i = 0; i < n; i++){
            for(char c : words[i].toCharArray()) {
                mask[i] |= 1 << (c - 'a');
            }
            for(int j = 0; j < i; j++){
                if((mask[i] & mask[j]) == 0){
                    ans = Math.max(ans, words[i].length() * words[j].length());
                }
            }
        }
        return ans;
    }
}

复杂度分析：

时间复杂度： O(n^2 + L)，其中 n 是字符串数组 words 的长度，而 L 是字符串数组所有字符串的长度之和。

空间复杂度： O(n)。

相关链接

• 318. 最大单词长度乘积