Python算法：选取字符串数组元素拼接无重复字符最长串

给定字符串数组，选取数组中若干字符串拼接得到新字符串S，要求S中所有字符互不重复，求S的最大可能长度。
例如输入['co', 'dil', 'ity']时，符合要求的S可以是codil、dilco等，最长长度为5。

• 先做预处理：数组里如果有字符串自身就包含重复字符，比如aab，这种字符串不可能出现在最终结果里，直接筛掉即可。同时把每个合法字符串转换成26位二进制掩码（对应a-z每个字母是否出现），方便后续快速判断字符是否重复。
• 用深度优先搜索遍历所有选/不选每个字符串的组合：
  • 如果当前字符串的字符和已经选中的字符没有重叠，就可以选中这个字符串，更新当前已选的字符集合和总长度，继续遍历后续字符串
  • 也可以选择不选当前字符串，直接遍历后续字符串
• 加剪枝优化提升效率：
  因为英文字母一共26个，一旦当前拼接长度到了26，直接返回即可，不可能有更长的合法串；用位运算做重复判断，两个掩码做按位与运算结果为0就代表没有重复字符，比操作集合快很多。

def max_unique_length(arr):
    # 预处理合法字符串，存储为(位掩码, 字符串长度)
    valid_str = []
    for s in arr:
        mask = 0
        is_valid = True
        for c in s:
            bit_pos = ord(c) - ord('a')
            # 当前串本身有重复字符，直接标记无效
            if (mask >> bit_pos) & 1:
                is_valid = False
                break
            mask |= 1 << bit_pos
        if is_valid:
            valid_str.append((mask, len(s)))
    
    max_res = 0
    total = len(valid_str)

    def backtrack(idx, cur_mask, cur_len):
        nonlocal max_res
        # 凑齐26个不重复字母，直接终止
        if cur_len == 26:
            max_res = 26
            return
        # 遍历完所有选项，更新最大值
        if idx == total:
            max_res = max(max_res, cur_len)
            return
        # 分支1：不选当前字符串
        backtrack(idx + 1, cur_mask, cur_len)
        # 分支2：无重复字符的前提下，选当前字符串
        s_mask, s_len = valid_str[idx]
        if cur_mask & s_mask == 0:
            backtrack(idx + 1, cur_mask | s_mask, cur_len + s_len)
    
    backtrack(0, 0, 0)
    return max_res

# 测试示例
if __name__ == "__main__":
    print(max_unique_length(['co', 'dil', 'ity']))  # 输出结果为5

这个实现对于数组长度不超过16的场景运行速度非常快，日常使用、面试答题都完全适用；如果数组长度更大，可以再加记忆化或者状态压缩的优化，但常规场景下这个写法已经是可读性和效率平衡的最优直观实现。

内容的提问来源于stack exchange，提问作者Adii_Mathur