给定一个字符串数组 arr，字符串 s 是将 arr 某一子序列字符串连接所得的字符串，如果 s 中的每一个字符都只出现过一次，那么它就是一个可行解。
请返回所有可行解 s 中最长长度。
示例 1：
输入：arr = ["un","iq","ue"] 输出：4 解释：所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique"，最大长度为 4。
示例 2：
输入：arr = ["cha","r","act","ers"] 输出：6 解释：可能的解答有 "chaers" 和 "acters"。
示例 3：
输入：arr = ["abcdefghijklmnopqrstuvwxyz"] 输出：26
提示：
1 <= arr.length <= 161 <= arr[i].length <= 26arr[i]中只含有小写英文字母
**难度**: Medium
**标签**: 位运算、 回溯算法、
# -*- coding: utf-8 -*-
# @Author : LG
"""
执行用时：156 ms, 在所有 Python3 提交中击败了34.91% 的用户
内存消耗：18.9 MB, 在所有 Python3 提交中击败了7.28% 的用户
解题思路：
回溯
"""
class Solution:
def maxLength(self, arr: List[str]) -> int:
results = [] # 用于存放所有结果
n = len(arr)
def backtrack(begin, current:str): # 起始位置，当前合并字符串
results.append(current) # 把当前结果存入最终结果中
if begin == n: # 如果遍历结束，则结束
return
for i in range(begin, n): # 从起始位置一直向后遍历
if len(set(current+arr[i])) != len(current+arr[i]): # 如果当前字符串存在重复元素，则跳出，继续下一个
continue
backtrack(i, current+arr[i]) # 处理下一个字符串
# 因为是字符串，且，传入的是current+arr[i], 这里不需要进行额外处理
backtrack(0, '')
result = 0
for r in results:
if len(r) > result:
result = len(r)
return result
"""
执行用时：156 ms, 在所有 Python3 提交中击败了34.91% 的用户
内存消耗：13.5 MB, 在所有 Python3 提交中击败了96.12% 的用户
代码经过精简后
"""
class Solution:
def maxLength(self, arr: List[str]) -> int:
self.result = 0
n = len(arr)
def backtrack(begin, current:str):
if len(current) > self.result:
self.result = len(current)
for i in range(begin, n):
if len(set(current+arr[i])) != len(current+arr[i]):
continue
backtrack(i, current+arr[i])
backtrack(0, '')
return self.result