最大单词长度乘积如何用位掩码判断两个单词是否无公共字母？
简化版
每个单词可以用 26 位 bitmask 表示包含哪些小写字母。两个单词没有公共字母，当且仅当 (mask1 & mask2) == 0。枚举单词对，满足无交集时更新长度乘积最大值。
详细版
构建单词 mask 时，字符 c 对应第 c-'a' 位。一个单词里某个字母出现多次也只会让对应位为 1，不影响集合表示。预处理所有单词 mask 后，双层枚举单词对，用按位与快速判断字母集合是否相交。
时间复杂度 O(totalChars + n^2)，空间复杂度 O(n)。优化点是相同 mask 只保留最大单词长度，可以减少比较次数。
完整版教学
一、为什么字母集合适合用 bitmask
题目只涉及 26 个小写字母，每个字母只有“出现/未出现”两种状态。用 26 位整数表示集合非常自然。
a -> 第 0 位
b -> 第 1 位
z -> 第 25 位例如单词 "abca" 的集合其实是 {a,b,c}，mask 低三位为 1。
二、如何构建单词 mask
遍历单词中的每个字符 c：
mask |= 1 << (c - 'a')|= 会把对应位设置为 1。即使同一个字母出现多次，也不会改变结果。
| 单词 | 字母集合 | mask 直观表示 |
|---|---|---|
abc | {a,b,c} | 低 3 位为 1 |
foo | {f,o} | f 和 o 对应位为 1 |
记忆钩子：用 bitmask 表示集合时，重复元素天然被去重。
三、为什么按位与能判断是否有公共字母
如果两个单词某个字母都出现，那么它们的 mask 在对应位都是 1。按位与后，这一位仍然是 1。
mask1 & mask2 == 0 => 没有任何公共 1 位例如：
abc: 00111
de : 11000
& 00000 => 无公共字母这比用 HashSet 逐字符判断更紧凑。
四、代码模板
int maxProduct(String[] words) {
int n = words.length;
int[] masks = new int[n];
for (int i = 0; i < n; i++) {
int mask = 0;
for (char c : words[i].toCharArray()) {
mask |= 1 << (c - 'a');
}
masks[i] = mask;
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if ((masks[i] & masks[j]) == 0) {
ans = Math.max(ans, words[i].length() * words[j].length());
}
}
}
return ans;
}双层枚举仍然是 O(n^2)，但交集判断变成了常数时间。
五、用数字例子推演
words=["abcw","baz","foo","bar","xtfn","abcdef"]。
"abcw" mask 包含 a,b,c,w
"xtfn" mask 包含 x,t,f,n
二者按位与为 0
乘积 = 4 * 4 = 16"abcw" 和 "abcdef" 有 a,b,c 公共字母，按位与不为 0，不能作为候选。
六、相同 mask 如何优化
如果多个单词字母集合相同，只需要保留最大长度。因为对外判断交集时，同一个 mask 的表现完全一样，长度越大越有利。
mask -> maxLength| 情况 | 是否需要保留多个 |
|---|---|
| 相同 mask，不同长度 | 保留最大长度 |
| 不同 mask | 都可能影响答案 |
这样可以减少后续 pair 数量。
七、常见误区与追问
- 误区：用异或判断无公共字母。 异或不能判断交集，按位与才是交集。
- 误区：重复字母导致长度计算错误。 mask 只用于集合判断，乘积仍用原单词长度。
- 误区：字符位移没有括号。
1 << c - 'a'可读性差，推荐写1 << (c-'a')。 - 追问：为什么 int 足够？ 26 个小写字母只需要 26 位，int 足够。
- 追问：如果有大小写或更多字符怎么办？ 可能需要 long、BitSet 或多个整数。
- 追问：复杂度瓶颈在哪？ 预处理是字符总数，主要瓶颈是单词对枚举
O(n^2)。
八、加强记忆
最大单词长度乘积的关键是把“字母集合是否相交”变成 (mask1 & mask2) == 0。每个单词一个 26 位集合，重复字母天然去重；交集为空才计算长度乘积。记住按位与表示集合交集，不要拿异或来判断无公共元素。