力扣318 最大单词长度乘积

给你一个字符串数组 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

解释：不存在这样的两个单词。

思路：

将字符串转换为位表示：
对于每个字符串，我们可以使用一个32位的整数来表示它包含的字母。对于小写字母，可以使用位运算（左移）将每个字母映射到一个唯一的位置。例如，'a'可以映射到第0位，'b'到第1位，依此类推。如果字符串中包含某个字母，则对应位置的位被设置为1，否则为0。

使用HashMap存储位表示和字符串长度：
我们使用一个HashMap，其中键是字符串的位表示，值是该字符串的长度。在遍历字符串数组时，我们将每个字符串转换为位表示，然后将位表示和字符串长度存储到HashMap中。如果同一个位表示已经在HashMap中存在，我们只保留较长的字符串长度。

找到没有相同字母的字符串对：
现在，我们有了一个包含位表示和对应字符串长度的HashMap。接下来，我们遍历HashMap中的所有位表示，对于每一对位表示，我们检查它们是否有相同的字母。我们使用位运算a & b == 0来检查两个位表示是否没有相同的字母。如果没有相同的字母，我们计算对应字符串长度的乘积，并更新一个变量（例如ans）来保留最大的乘积。

返回结果：
最后，返回计算得到的最大乘积。

这种方法的关键在于利用位运算快速判断两个字符串是否有相同的字母，从而避免了暴力比较所有字母的复杂度，大大提高了算法的效率。同时，使用HashMap来存储位表示和字符串长度，可以方便快速地查找和更新。

代码

class Solution {
    public int maxProduct(String[] words) {
        Map<Integer,Integer> map = new HashMap<>();
        for(String w:words){
            int t=0,m=w.length();
            for(int i=0;i<m;i++){
                int u=w.charAt(i)-'a';
                t |=(1<<u);
            }
            if(!map.containsKey(t) || map.get(t)<m ) map.put(t,m);
        }
        int ans=0;
        for(int a:map.keySet()){
            for(int b:map.keySet()){
               if((a&b)==0) ans = Math.max(ans,map.get(a)*map.get(b));
               } 
        }
        return ans;
    }
}