题目重点：对应 Netflix Member 组 Coding 的 string pair 题，给出 Unicode 通用集合基线与仅小写 a–z 时 26 位掩码优化，分析输出下界。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版返回原列表下标 pair `(i,j)` 且 i<j；如果题目只要数量，可直接计数不保留输出。
- 一般版本按 Unicode code point 精确比较、大小写不合并；bitmask 版本仅允许 ASCII 小写 a–z，否则抛错。
- 空字符串与任意字符串无共同字符；重复字符串位于不同下标，仍是不同输入元素。
解题路线
- 先把每个字符串转为字符集合，再枚举所有 i<j，用 set.isdisjoint 检查是否没有交集。这样字符重复不影响结果。
- 若确定字母表只有 26 个小写字母，为每串构造 26 位整数，第 c 位标记是否出现；两串按位与为零即无共同字符。先检查输入范围，不能让任意 Unicode 字符直接映射错误位。
- U 个不同字符掩码时，可按 mask 聚合相同字符串并计算 pair 数以减少重复比较；但如果必须返回全部 pair，输出可能 Θ(n²)，无法普遍规避。
手动走一遍
[ab,cd,bc,""] 中 ab 与 cd 无公共字符，ab 与 bc 共享 b 不合格；空串与另外三串都合格。小写版本 mask(ab)=000...011，mask(cd)=000...1100，按位与为 0。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from itertools import combinations
def pairs_without_shared_characters(words):
"""Return index pairs; Unicode characters are treated as exact code points."""
letters = [set(word) for word in words]
return [(left, right) for left, right in combinations(range(len(words)), 2)
if letters[left].isdisjoint(letters[right])]
def lowercase_bitmask(word):
mask = 0
for char in word:
if not "a" <= char <= "z":
raise ValueError("bitmask variant requires lowercase ASCII")
mask |= 1 << (ord(char) - ord("a"))
return mask
def lowercase_pairs_with_bitmasks(words):
masks = [lowercase_bitmask(word) for word in words]
return [(left, right) for left, right in combinations(range(len(words)), 2)
if masks[left] & masks[right] == 0]
复杂度
预处理所有字符 O(L)，L 为总字符数；一般集合两两判断最坏 O(n²A)，A 为较小集合大小，额外空间 O(L+P)。26 位掩码版本预处理 O(L)、比较 O(n²) 常数位运算、输出空间 O(P)；P 可能 Θ(n²)。
易错点与追问
容易失分的边界
- 比较字符串本身是否相等，而不是字符集合是否相交。
- 两个相同字符在一个串内重复出现，误当两串有共同字符。
- 对大写、数字、中文直接使用 a–z 的位偏移。
- 只给 pair 数量却声称算法能低于所有输出 pair 的下界。
继续深挖
- 若字母表有上千字符，可怎样用动态 bitset 或 Roaring bitmap？
- 只需计数时，按相同 mask 分组能减少多少比较？
- 字符串总数很大但每串字符很少，倒排索引可如何剪枝？
