Meta AI Coding：最大不重复字符单词子集

题目重点：选择字符互不重复的单词子集，比较回溯、位掩码与迭代状态去重，分析字符集上界与最坏复杂度。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

输入是一组小写英文字母与数字构成的词；若一个词内部已有重复字符，就不能选这个词。
任意两个被选词的字符集合不能相交；目标是最大化合并后的不同字符数，若有多个最优解返回任意一个。
示例接口返回原词列表；helper bug和工程文件结构需结合实际代码确认，本文明确实现solver核心。

解题路线

把 26 个小写字母和 10 个数字映射到 36 位掩码。预处理每个词，遇到词内重复字符就跳过。
用 states 保存每个可达的已用字符掩码，以及达到该掩码的一组选词下标。遍历新词时，基于当前状态快照扩展不相交的掩码。
相同掩码只保留一个见证解，最终取 bit_count 最大的掩码。迭代实现避免递归深度问题；达到 36 个不同字符可提前结束。

手动走一遍

对 [ab, cd, ac]，先选 ab 得到掩码 {a,b}，再选 cd 得到 {a,b,c,d}；ac 与 ab 冲突，但单独选 ac 仍是合法状态。最终返回 [ab, cd]，覆盖四个不同字符。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def maximum_unique_word_subset(words):
    """Return one largest-character subset without repeated characters."""
    alphabet = "abcdefghijklmnopqrstuvwxyz0123456789"
    positions = {character: index for index, character in enumerate(alphabet)}
    states = {0: ()}  # used-character mask -> selected word indices

    for index, word in enumerate(words):
        mask = 0
        for character in word:
            if character not in positions:
                raise ValueError("only lowercase letters and digits are supported")
            bit = 1 << positions[character]
            if mask & bit:
                mask = None  # This word repeats a character internally.
                break
            mask |= bit
        if mask is None:
            continue
        for used, selected in list(states.items()):
            if used & mask == 0:
                states.setdefault(used | mask, selected + (index,))
        if (1 << len(alphabet)) - 1 in states:
            break

    best = max(states, key=int.bit_count)
    return [words[index] for index in states[best]]

复杂度

设有效词数为 n、不同可达掩码数最大为 S、字符集大小为 36。预处理为 O(总字符数)，迭代扩展最坏 O(nS)，S 上界为 2^36；保存每个掩码及其见证下标需要 O(Sn) 的最坏空间。字符集上界使位掩码可用，并不保证所有输入都能快速求完。

易错点与追问

容易失分的边界

只检查词与此前词是否相交，漏掉一个词内部的重复字符，会产生非法答案。
边遍历 states 边直接修改字典，会重复使用当前词或触发迭代错误；先取状态快照。
已知输入字符集为数字和小写字母；这只能提供至多 36 个不同字符的提前终止条件，不能证明递归一定不会爆栈。

继续深挖

若只求最大数量、不需输出词，可以只维护掩码集合，减少见证路径内存。
若输入规模大而有效字符数少，可按词掩码去重，并用分支定界的剩余字符上界剪枝；仍需说明指数级最坏情况。