难度: Medium
给定一个字符串数组 arr，字符串 s 是将 arr 的含有 不同字母 的 子序列 字符串 连接 所得的字符串。
请返回所有可行解 s 中最长长度。
子序列 是一种可以从另一个数组派生而来的数组，通过删除某些元素或不删除元素而不改变其余元素的顺序。
示例 1：
输入：arr = ["un","iq","ue"]
输出：4
解释：所有可能的串联组合是：
- ""
- "un"
- "iq"
- "ue"
- "uniq" ("un" + "iq")
- "ique" ("iq" + "ue")
最大长度为 4。
示例 2：
输入：arr = ["cha","r","act","ers"] 输出：6 解释：可能的解答有 "chaers" 和 "acters"。
示例 3：
输入：arr = ["abcdefghijklmnopqrstuvwxyz"] 输出：26
提示：
1 <= arr.length <= 161 <= arr[i].length <= 26arr[i] 中只含有小写英文字母运行时间: 50 ms
内存: 0.0 MB
from typing import List
class Solution:
def maxLength(self, arr: List[str]) -> int:
max_length = 0
bitmasks = [0]
for s in arr:
bitmask = 0
for char in s:
bit = 1 << (ord(char) - ord('a'))
if bitmask & bit:
bitmask = 0 # Skip strings with duplicate characters
break
bitmask |= bit
if bitmask == 0:
continue
new_bitmasks = []
for existing_mask in bitmasks:
if existing_mask & bitmask == 0:
new_mask = existing_mask | bitmask
new_bitmasks.append(new_mask)
max_length = max(max_length, bin(new_mask).count('1'))
bitmasks.extend(new_bitmasks)
return max_length
这个题解使用了位掩码(bitmask)来表示字符串中各个字符的存在情况。每个英文字母对应位掩码中的一个位，如果字符存在，则该位为1，否则为0。这种方法可以快速检查两个字符串是否有重复字符，只需将两个位掩码进行与操作(&)即可。算法首先将每个字符串转换为位掩码，忽略包含重复字符的字符串。然后，通过尝试将每个有效的新字符串掩码与已存在的掩码组合，并检查它们是否兼容（即无重叠位）。如果兼容，就合并这两个掩码，并更新最大长度。这种方法利用了位运算的高效性，适合解决这类问题。
时间复杂度: O(n * 2^n)
空间复杂度: O(2^n)
from typing import List
class Solution:
def maxLength(self, arr: List[str]) -> int:
max_length = 0 # 最大长度的初始化
bitmasks = [0] # 存储不同字符组合的掩码列表
for s in arr:
bitmask = 0 # 当前字符串的位掩码
for char in s:
bit = 1 << (ord(char) - ord('a')) # 为当前字符生成位
if bitmask & bit:
bitmask = 0 # 如果字符已存在，跳过这个字符串
break
bitmask |= bit # 添加当前字符到掩码中
if bitmask == 0:
continue # 如果字符串有重复字符，忽略它
new_bitmasks = []
for existing_mask in bitmasks:
if existing_mask & bitmask == 0: # 检查现有掩码和新掩码是否兼容
new_mask = existing_mask | bitmask # 合并掩码
new_bitmasks.append(new_mask)
max_length = max(max_length, bin(new_mask).count('1')) # 更新最大长度
bitmasks.extend(new_bitmasks) # 将新的合法掩码添加到列表中
return max_length # 返回找到的最大长度
位掩码在处理字符集合时提供了高效的空间和时间性能。相比于哈希表和数组，位掩码可以在常数时间内进行字符的检查、添加和组合操作。此外，位运算如与、或和异或操作可以非常迅速地执行，适合频繁的字符集合合并和交集检查。这些操作在哈希表或数组中会更复杂和耗时。位掩码也更节省空间，因为它只使用一个整数来表示字符的存在情况，而不需要额外的数据结构。
题目的解决方案假设只处理小写英文字母。如果需要处理超过26个字母的情况，包括特殊字符或大写字母，我们需要扩展位掩码的范围。例如，可以使用一个较大的整数类型或者多个整数来表示更多的字符。每个不同的字符，包括大写字母和特殊字符，都可以映射到不同的位上。然而，这需要额外的处理逻辑来确保每个字符都正确地映射和管理。
不会。忽略包含重复字符的字符串是基于问题的要求：寻找不含重复字符的最长字符串组合。包含重复字符的字符串本身就不符合要求，不能作为有效的组合部分。因此，忽略这些字符串不会影响寻找不包含重复字符的最长组合。实际上，这种策略有助于减少不必要的计算和存储，提高算法的效率。
在合并两个兼容的位掩码（即没有重叠的位）后，通过计算合并后的位掩码中1的数量来确定合并字符串的长度。这一长度是将两个不含重复字符的字符串合并后的结果。每次合并时，算法都会检查这个新长度是否超过了当前记录的最大长度，并在必要时更新最大长度。这确保了每次合并后，我们都有机会捕捉到可能的最大长度。