Given an array of strings arr. String s is a concatenation of a sub-sequence of arr which have unique characters.
Return the maximum possible length of s.
 
Example 1:
Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
Maximum length is 4.

Example 2:
Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible solutions are "chaers" and "acters".

Example 3:
Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26

 
Constraints:

1 <= arr.length <= 16
1 <= arr[i].length <= 26
arr[i] contains only lower case English letters.

Difficulty: MEDIUM
Tags: String algorithms

Bit manipulation

Data structures

Complete search
Skill types: Bit manipulation

Data structures

Complete search

Starter code:
class Solution:
    def maxLength(self, arr: List[str]) -> int:
        

Solutions:
class Solution:

	def maxLength(self, arr: List[str]) -> int:

		def digit_representation(s):
			ans = 0
			for c in s:
				ans |= 1 << ord(c) - ord('a')
			return ans
		A = sorted([(len(s), digit_representation(s)) for s in set(arr) if len(set(s)) == len(s)], reverse=True)
		if not A:
			return 0
		R = [sum((t[0] for t in A))]
		for i in range(1, len(A)):
			R.append(R[-1] - A[i][0])
		self.ans = A[0][0]

		def helper(i, b, k):
			if i == len(A):
				self.ans = max(self.ans, k)
			elif k + R[i] > self.ans:
				if not b & A[i][1]:
					helper(i + 1, b | A[i][1], k + A[i][0])
				helper(i + 1, b, k)
		helper(0, 0, 0)
		return self.ans


from typing import List

class Solution:

	def helper(self, current, arr, index, chars, remaining):
		if index == len(arr):
			return current
		maxLength = current
		for i in range(index, len(arr), 1):
			remaining -= len(arr[i])
			if current + len(arr[i]) + remaining <= maxLength:
				continue
			isGood = True
			for c in arr[i]:
				if c in chars:
					isGood = False
					break
			if isGood:
				for c in arr[i]:
					chars.add(c)
				maxLength = max(self.helper(current + len(arr[i]), arr, i + 1, chars, remaining), maxLength)
				for c in arr[i]:
					chars.remove(c)
		return maxLength

	def maxLength(self, arr: List[str]) -> int:
		arr = [a for a in arr if len(a) == len(set(a))]
		remaining = sum([len(a) for a in arr])
		return self.helper(0, arr, 0, set(), remaining)


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		uniqELements = ['']
		maximum = 0
		for i in range(len(arr)):
			sz = len(uniqELements)
			for j in range(sz):
				x = arr[i] + uniqELements[j]
				if len(x) == len(set(x)):
					uniqELements.append(x)
					maximum = max(maximum, len(x))
		return maximum


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		arr_sets = [set(x) for x in arr]

		def buildSet(bitlist):
			output = set()
			for (i, bit) in enumerate(bitlist):
				if bit:
					output = output.union(arr_sets[i])
			return output

		def recurse(bitlist, index):
			if index == len(arr):
				return len(buildSet(bitlist))
			new_bitlist = bitlist[:]
			new_bitlist[index] = 0
			not_included = recurse(new_bitlist, index + 1)
			if len(arr_sets[index]) != len(arr[index]) or buildSet(bitlist).intersection(arr_sets[index]):
				return not_included
			else:
				new_bitlist[index] = 1
				return max(not_included, recurse(new_bitlist, index + 1))
		return recurse([0 for _ in arr], 0)


class Solution:

	def get_max_length(self, sets, idx, cur_set):
		if idx == len(sets):
			return len(cur_set)
		m = 0
		for i in range(idx, len(sets)):
			if not cur_set & sets[i]:
				res = self.get_max_length(sets, i + 1, cur_set.union(sets[i]))
			else:
				res = self.get_max_length(sets, i + 1, cur_set)
			m = max(m, res)
		return m

	def maxLength(self, arr: List[str]) -> int:
		sets = []
		for (i, s) in enumerate(arr):
			t = set()
			for ch in s:
				if ch in t:
					break
				else:
					t.add(ch)
			else:
				sets.append(t)
		print(sets)
		return self.get_max_length(sets, 0, set())


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		arr = [set(x) for x in arr if len(x) == len(set(x))]
		mx = 0

		def util(start, cur):
			nonlocal mx
			if start == len(arr):
				mx = max(mx, len(cur))
			for i in range(start, len(arr)):
				if cur & arr[i]:
					continue
				cur |= arr[i]
				util(i + 1, cur)
				cur ^= arr[i]
			mx = max(mx, len(cur))
		util(0, set())
		return mx


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		res = 0

		def dfs(n, s, l, cur):
			nonlocal res
			if n == l:
				if len(set(cur)) == len(cur):
					res = max(res, len(cur))
				return
			for i in range(s, len(arr)):
				new_cur = cur + arr[i]
				if len(set(cur)) != len(cur):
					return
				dfs(n, i + 1, l + 1, new_cur)
		for i in range(len(arr) + 1):
			dfs(i, 0, 0, '')
		return res


class Solution:

	def recurse(self, arr, cur):
		for (i, x) in enumerate(arr):
			if cur.intersection(x):
				continue
			nxt = cur.union(x)
			nxt_key = ''.join(sorted(nxt))
			if nxt_key not in self.visited:
				self.visited.add(nxt_key)
				self.maxlen = max(self.maxlen, len(nxt))
				self.recurse(arr[:i] + arr[i + 1:], nxt)

	def maxLength(self, arr: List[str]) -> int:
		arr = [set(x) for x in arr if len(set(x)) == len(x)]
		self.maxlen = 0
		self.visited = set()
		self.recurse(arr, set())
		return self.maxlen


class Solution:

	def is_unique(self, s):
		return len(set(s)) == len(s)

	def maxLength(self, arr: List[str]) -> int:
		dct = {}
		maxVal = 0
		for i in range(0, len(arr)):
			v = frozenset(arr[i])
			if self.is_unique(arr[i]):
				maxVal = max(maxVal, len(v))
			for j in range(i + 1, len(arr)):
				t = arr[i] + arr[j]
				val = frozenset(t)
				if self.is_unique(t):
					arr.append(t)
					maxVal = max(maxVal, len(val))
		return maxVal


from collections import Counter

class Solution:

	def dfs(self, arr, cur):
		for (i, string_set) in enumerate(arr):
			if cur.intersection(string_set):
				continue
			nxt = cur.union(string_set)
			nxt_key = ''.join(sorted(nxt))
			if nxt_key not in self.visited:
				self.visited.add(nxt_key)
				self.ans = max(self.ans, len(nxt))
				self.dfs(arr[:i] + arr[i:], nxt)

	def maxLength(self, arr: List[str]) -> int:
		new_arr = []
		for string in arr:
			string_set = set(string)
			if len(string_set) == len(string):
				new_arr.append(string_set)
		arr = new_arr
		self.visited = set()
		self.ans = 0
		self.dfs(arr, set())
		return self.ans


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		filtered = []
		for string in arr:
			seen = {}
			good = True
			for letter in string:
				if letter in seen:
					good = False
				else:
					seen[letter] = True
			if good:
				filtered.append(string)
		self.memo = {}
		print(filtered)
		return self.getLength(0, filtered, {})

	def getLength(self, current, arr, used):
		if not arr:
			return current
		if tuple(arr) in self.memo:
			return self.memo[tuple(arr)]
		maxi = current
		for index in range(len(arr)):
			string = arr[index]
			possible = True
			for char in string:
				if char in used:
					possible = False
			if not possible:
				continue
			for char in string:
				used[char] = True
			result = self.getLength(current + len(string), arr[:index] + arr[index + 1:], used)
			if result > maxi:
				maxi = result
			for char in string:
				del used[char]
		self.memo[tuple(arr)] = maxi
		return maxi


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		dp = defaultdict(lambda : set())

		def dfs(index, cur):
			if index == len(arr) or cur in dp[index]:
				return len(cur)
			dp[index].add(cur)
			best = len(cur)
			for x in range(index, len(arr)):
				count = Counter(cur)
				xCount = Counter(arr[x])
				canTake = True
				for (k, v) in xCount.items():
					if k in count or v > 1:
						canTake = False
				if canTake:
					best = max(best, dfs(x + 1, cur + arr[x]))
				best = max(best, dfs(x + 1, cur))
			return best
		return dfs(0, '')


class Solution:

	def maxLength(self, arr: List[str]) -> int:

		def score(s):
			return sum((1 << ord(c) - ord('a') for c in s))

		def valid(s):
			return collections.Counter(s).most_common()[0][1] <= 1
		arr = [s for s in arr if valid(s)]
		s = [score(s) for s in arr]
		res = 0
		for i in range(2 ** len(s)):
			val = 0
			cur = 0
			for j in range(len(s)):
				if 1 << j & i == 0:
					continue
				if s[j] & val:
					break
				val |= s[j]
				cur += len(arr[j])
			else:
				res = max(res, cur)
		return res


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		self.out = set()
		self.visited = set()
		opts = []
		for sub in arr:
			tmp = set()
			omit = False
			for ch in sub:
				if ch in tmp:
					omit = True
				tmp.add(ch)
			if not omit:
				opts.append(tmp)
		self.dfs(set(), opts)
		return len(self.out)

	def dfs(self, curr, opts):
		if tuple(sorted(curr)) in self.visited:
			return
		self.visited.add(tuple(sorted(curr)))
		if len(curr) > len(self.out):
			self.out = curr
		if not opts:
			return
		for (j, opt) in enumerate(opts):
			if not curr.intersection(opt):
				self.dfs(curr.union(opt), opts[:j] + opts[j + 1:])


class Solution:
	from collections import Counter

	def maxLength(self, arr: List[str]) -> int:
		st = [(None, 0)]
		l = 0
		ind_dic = {}
		new_ind = 0
		for i in range(len(arr)):
			ind_dic[i] = Counter(arr[i])
		while st:
			(sub, ind) = st.pop(0)
			if sub:
				l = max(l, len(sub))
			if ind >= len(arr):
				continue
			if not sub:
				st.append((None, ind + 1))
				if len(arr[ind]) == len(set(arr[ind])):
					st.append((arr[ind], ind + 1))
			else:
				cur_dic = Counter(sub)
				if set(cur_dic.keys()).intersection(set(ind_dic[ind].keys())):
					st.append((sub, ind + 1))
				elif len(arr[ind]) > len(set(arr[ind])):
					st.append((sub, ind + 1))
				else:
					st.append((sub + arr[ind], ind + 1))
					st.append((sub, ind + 1))
			new_ind = ind
		return l


from typing import List

class Solution:

	def uniqueLength(self, string: str) -> int:
		for i in range(len(string)):
			if string.count(string[i]) > 1:
				return -1
		else:
			return len(string)

	def maxUnique(self, arr: List[str], index: int, curr_string: str, result: List[int]) -> List[int]:
		if index == len(arr) and self.uniqueLength(curr_string) > result[0]:
			result[0] = len(curr_string)
			return
		if index == len(arr):
			return
		self.maxUnique(arr, index + 1, curr_string, result)
		self.maxUnique(arr, index + 1, curr_string + arr[index], result)

	def maxLength(self, arr: List[str]) -> int:
		result = [0] * 1
		self.maxUnique(arr, 0, '', result)
		return result[0]


class Solution:

	def recurse(self, letters, arr, csum):
		keys_as_str = ''.join(sorted(letters))
		if keys_as_str not in self.visited:
			self.visited.add(keys_as_str)
			self.max_len = max(self.max_len, csum)
			for (i, new_letters) in enumerate(arr):
				if len(new_letters.intersection(letters)) > 0:
					continue
				self.recurse(new_letters.union(letters), arr[:i] + arr[i + 1:], csum + len(new_letters))

	def maxLength(self, arr: List[str]) -> int:
		new_arr = []
		for word in arr:
			word_set = set(word)
			if len(word_set) == len(word):
				new_arr.append(word_set)
		self.max_len = 0
		self.visited = set()
		for (i, letters) in enumerate(new_arr):
			self.recurse(letters, new_arr[:i] + new_arr[i + 1:], len(letters))
		return self.max_len


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		if len(arr) == 0:
			return 0
		currRes = []
		for el in arr:
			if self.isUnique(el):
				currRes.append(el)
		for el in arr:
			for subSeq in currRes:
				if self.isUnique(el + subSeq):
					currRes.append(el + subSeq)
		res = 0
		for el in currRes:
			res = max(res, len(el))
		return res

	def isUnique(self, s):
		return len(set(s)) == len(s)


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		return self.backtrack(set(), arr, 0)

	def backtrack(self, curr, arr, index):
		if index >= len(arr):
			return len(curr)
		max_len = 0
		for i in range(index, len(arr)):
			char_set = set(arr[i])
			if curr.intersection(char_set) == set() and len(char_set) == len(arr[i]):
				curr = curr.union(char_set)
				max_len = max(max_len, self.backtrack(set(curr), arr, i + 1))
				curr = curr.difference(char_set)
			else:
				max_len = max(max_len, self.backtrack(curr, arr, i + 1))
		return max_len


class Solution(object):

	def maxLength(self, arr):

		def get_max_len(arr):
			dp = [set(x) for x in arr if len(set(x)) == len(x)]
			for v in arr:
				if len((a := set(v))) == len(v):
					for b in dp:
						if a & b:
							continue
						dp.append(a | b)
			return max((len(x) for x in dp)) if dp else 0
		return get_max_len(arr)


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		a = [set(i) for i in arr if len(set(i)) == len(i)]
		n = len(a)
		an = 0
		for v in range(1, 2 ** n):
			s = set()
			i = 0
			while v > 0:
				if v & 1 == 1:
					if s & a[i]:
						break
					s = s ^ a[i]
				v = v >> 1
				i += 1
			an = max(an, len(s))
		return an


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		return self.recursive(arr, '', 0)

	def recursive(self, arr, curr_str, pick_idx):
		if pick_idx == len(arr):
			table = {}
			for ch in curr_str:
				if ch in table:
					return 0
				table[ch] = True
			return len(curr_str)
		return max(self.recursive(arr, curr_str + arr[pick_idx], pick_idx + 1), self.recursive(arr, curr_str, pick_idx + 1))


class Solution:

	def maxLength(self, arr: List[str]) -> int:

		def dfs(arr, path, res):
			if self.checkUnique(path):
				res.append(path)
			for i in range(len(arr)):
				dfs(arr[i + 1:], path + arr[i], res)
		(concatenated_string, res) = ([], 0)
		dfs(arr, '', concatenated_string)
		for elem in concatenated_string:
			res = max(res, len(elem))
		return res

	def checkUnique(self, string):
		dic = dict()
		for ch in string:
			if ch not in dic:
				dic[ch] = 1
			else:
				return False
		return True


class Solution:

	def maxLength(self, arr: List[str]) -> int:

		def isUniqueChars(s):
			return len(set(s)) == len(s)
		arr = [set(w) for w in arr if isUniqueChars(w)]
		results = list(arr)
		for w in arr:
			temp = []
			for r in results:
				if not w.intersection(r):
					temp.append(w.union(r))
			results = results + temp
		max_length = 0
		for w in results:
			max_length = max(max_length, len(w))
		return max_length


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		dp = [set()]
		for a in arr:
			if len(set(a)) < len(a):
				continue
			a = set(a)
			for c in dp[:]:
				if a & c:
					continue
				dp.append(a | c)
		return max((len(a) for a in dp))
		return self.m


class Solution:
	count = 0

	def dfs(self, arr, i, visited):
		for index in range(i + 1, len(arr)):
			visit = True
			for j in range(0, len(arr[index])):
				if arr[index][j] in visited:
					for k in range(0, j):
						visited.remove(arr[index][k])
					visit = False
					break
				else:
					visited.add(arr[index][j])
			if visit:
				self.count = max(self.count, len(visited))
			self.dfs(arr, index, visited)
			for char in arr[index]:
				if char in visited and visit:
					visited.remove(char)

	def maxLength(self, arr: List[str]) -> int:
		if len(arr) == 0:
			return 0
		visited = set()
		self.count = 0
		self.dfs(arr, -1, visited)
		return self.count


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		if len(arr) == 0:
			return 0
		currRes = []
		for el in arr:
			if self.isUnique(el):
				currRes.append(el)
		for el in arr:
			for subSeq in currRes:
				if self.isUnique(el + subSeq):
					currRes.append(el + subSeq)
		res = 0
		for el in currRes:
			res = max(res, len(el))
		return res

	def isUnique(self, s):
		chars = set()
		for c in s:
			if c not in chars:
				chars.add(c)
			else:
				return False
		return True


class Solution:

	def maxLength(self, arr):

		def powerset(iterable):
			import itertools
			s = list(iterable)
			return itertools.chain.from_iterable((itertools.combinations(s, r) for r in range(len(s) + 1)))
		result = 0
		for subset in powerset(arr):
			candidate = ''.join(subset)
			if len(candidate) > result and len(candidate) == len(set(candidate)):
				result = len(candidate)
		return result


class Solution:

	def maxLength(self, arr: List[str]) -> int:

		def isUnique(concatString):
			concatSet = set()
			for char in concatString:
				if char in concatSet:
					return False
				concatSet.add(char)
			return True
		length = len(arr)
		self.result = 0

		def dfs(index, curr):
			if isUnique(curr):
				self.result = max(self.result, len(curr))
			if index == length - 1:
				return
			for i in range(index + 1, length):
				dfs(i, curr + arr[i])
		for i in range(length):
			dfs(i, arr[i])
		return self.result


class Solution:

	def maxLength(self, arr: List[str]) -> int:

		def maxLength(i, string):
			nonlocal ans
			if i == len(arr):
				(s, invalid) = (set(), False)
				for ch in string:
					if ch in s:
						invalid = True
						break
					s.add(ch)
				if not invalid:
					ans = max(ans, len(string))
				return
			maxLength(i + 1, string)
			maxLength(i + 1, string + arr[i])
		ans = 0
		maxLength(0, '')
		return ans


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		if len(arr) == 1:
			if len(set(arr[0])) == len(list(arr[0])):
				return len(set(arr[0]))
			else:
				return 0
		all_combinations = []
		max_ = 0
		for r in range(1, len(arr) + 1):
			combinations_object = itertools.combinations(arr, r)
			combinations_list = list(combinations_object)
			for st in combinations_list:
				comb = ''.join(st)
				if len(set(comb)) == len(comb):
					max_ = max(max_, len(comb))
		return max_


class Solution:

	def is_unique(self, word):
		count = dict()
		for char in ''.join(word):
			if char in count:
				return False
			else:
				count[char] = 1
		return True

	def find_max(self, arr, output, current, start_index):
		if self.is_unique(current):
			output.append(len(''.join(current)))
		for i in range(start_index, len(arr)):
			self.find_max(arr, output, current + [arr[i]], i + 1)

	def maxLength(self, arr: List[str]) -> int:
		output = []
		self.find_max(arr, output, [], 0)
		return max(output)


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		self.maxLen = 0

		def isUnique(s):
			return len(s) if len(s) == len(set(s)) else -1

		def dfs(i, s):
			if i == len(candi) and isUnique(s) > self.maxLen:
				self.maxLen = len(s)
				return
			if i == len(candi):
				return
			dfs(i + 1, s)
			dfs(i + 1, s + candi[i])
		candi = []
		for ss in arr:
			if isUnique(ss) > 0:
				candi.append(ss)
		dfs(0, '')
		return self.maxLen


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		self.output = []
		self.res = 0
		self.dfs(arr)
		return self.res

	def checkUnique(self, s):
		m = set()
		for i in s:
			if i not in m:
				m.add(i)
			else:
				return False
		return True

	def dfs(self, arr, first=0, curr=[]):
		st = ''.join(curr)
		if self.checkUnique(st):
			self.output.append(st)
			self.res = max(len(st), self.res)
		for i in range(first, len(arr)):
			curr.append(arr[i])
			self.dfs(arr, i + 1, curr)
			curr.pop()


from itertools import combinations

class Solution:

	def maxLength(self, arr: List[str]) -> int:
		max_count = 0
		for i in range(0, len(arr) + 1):
			comb = combinations(arr, i)
			for c in comb:
				count = 0
				bag = set()
				s = ''.join(c)
				for k in s:
					if k in bag:
						count = 0
						break
					else:
						count += 1
						bag.add(k)
				max_count = max(max_count, count)
		return max_count


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		if not arr:
			return 0

		def isUnique(s):
			return len(set(s)) == len(s)

		def dfs(arr, res, curr):
			if isUnique(curr):
				res[0] = max(res[0], len(curr))
			for i in range(len(arr)):
				dfs(arr[i + 1:], res, curr + arr[i])
		res = [0]
		dfs(arr, res, '')
		return res[0]


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		self.ans = 0
		vis = set()

		def help(s, i):
			if len(s) == len(set(s)):
				self.ans = max(self.ans, len(s))
			if i >= len(arr):
				return
			for j in range(i, len(arr)):
				if j not in vis:
					vis.add(j)
					help(s + arr[j], j + 1)
					vis.remove(j)
		help('', 0)
		return self.ans


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		n = len(arr)
		self.max = 0

		def helper(idx, chars):
			if idx >= n:
				if len(chars) == len(set(chars)):
					self.max = max(self.max, len(chars))
			else:
				helper(idx + 1, chars)
				helper(idx + 1, chars + list(arr[idx]))
		helper(0, [])
		return self.max


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		self.maxLen = 0

		def isUnique(s):
			return len(s) if len(s) == len(set(s)) else -1

		def dfs(i, s):
			if i == len(arr) and isUnique(s) > self.maxLen:
				self.maxLen = len(s)
				return
			if i == len(arr):
				return
			dfs(i + 1, s)
			dfs(i + 1, s + arr[i])
		dfs(0, '')
		return self.maxLen


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		if arr == None:
			return
		path = []
		result = [0]

		def hasUniqueLetters(word):
			hash_set = set()
			for c in word:
				if c in hash_set:
					return False
				else:
					hash_set.add(c)
			return True

		def generateCombinations(arr, i, result, path):
			if i == len(arr):
				combination = ''.join(path)
				if path and hasUniqueLetters(combination):
					if result[0] < len(combination):
						result[0] = len(combination)
				return
			curr_path = []
			curr_path.extend(path)
			curr_path.append(arr[i])
			generateCombinations(arr, i + 1, result, path)
			generateCombinations(arr, i + 1, result, curr_path)
		generateCombinations(arr, 0, result, path)
		return result[0]


class Solution:

	def uniquelen(self, cur):
		if len(cur) == len(set(cur)):
			return len(cur)
		else:
			return -1

	def dfs(self, arr, index, cur):
		if index == len(arr) and self.uniquelen(cur) > self.ans:
			self.ans = self.uniquelen(cur)
			return
		if index == len(arr):
			return
		self.dfs(arr, index + 1, cur)
		self.dfs(arr, index + 1, cur + arr[index])

	def maxLength(self, arr: List[str]) -> int:
		self.ans = -1
		self.dfs(arr, 0, '')
		return self.ans


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		ret = [set()]
		for string in arr:
			curr = set(string)
			if len(curr) == len(string):
				for seen in ret:
					if not seen & curr:
						ret.append(seen | curr)
		max_len = 0
		for string in ret:
			max_len = max(max_len, len(string))
		return max_len


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		char_freq = {}
		for i in range(len(arr)):
			char_freq[i] = set()
			for c in arr[i]:
				if c not in char_freq[i]:
					char_freq[i].add(c)
				else:
					del char_freq[i]
					break
		items_count = len(char_freq)
		max_len = 0
		for i in range(1, 2 ** items_count):
			num = i
			current_set = set()
			current_len = 0
			for j in list(char_freq.keys()):
				intersect = current_set.intersection(char_freq[j])
				if num & 1 and (not intersect):
					current_set.update(char_freq[j])
					current_len += len(arr[j])
					max_len = max(max_len, current_len)
				elif num & 1 and intersect:
					break
				num >>= 1
		return max_len


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		if arr == None:
			return
		path = []
		result = [0]

		def generateCombinations(arr, i, result, path):
			if i == len(arr):
				if path:
					combination = ''.join(path)
					if len(set(combination)) == len(combination):
						if result[0] < len(combination):
							result[0] = len(combination)
				return
			curr_path = []
			curr_path.extend(path)
			curr_path.append(arr[i])
			generateCombinations(arr, i + 1, result, path)
			generateCombinations(arr, i + 1, result, curr_path)
		generateCombinations(arr, 0, result, path)
		return result[0]


class Solution:

	def maxLength(self, arr: List[str]) -> int:

		def valid(w):
			return all((v <= 1 for v in collections.Counter(w).values()))

		def dfs(i, cand):
			if i < 0:
				return 0
			res = dfs(i - 1, cand)
			if valid(arr[i]) and all((c in cand for c in arr[i])):
				new_cand = {c for c in cand if c not in collections.Counter(arr[i]).keys()}
				res = max(res, dfs(i - 1, new_cand) + len(arr[i]))
			return res
		return dfs(len(arr) - 1, {chr(i + ord('a')) for i in range(26)})


class Solution:

	def maxLength(self, arr):
		prev = {0: 0}
		for word in arr:
			seen = 0
			duplicate = False
			for char in word:
				binaryC = 1 << ord(char) - ord('a')
				if binaryC & seen != 0:
					duplicate = True
					break
				else:
					seen |= binaryC
			if duplicate:
				continue
			toAdd = dict()
			for k in prev:
				if k & seen == 0:
					toAdd[k | seen] = prev[k] + len(word)
			prev.update(toAdd)
		return max(prev.values())

class Solution:

	def maxLength(self, arr):
		cands = {0: 0}
		for word in arr:
			if len(word) != len(set(word)):
				continue
			currW = sum((1 << ord(char) - ord('a') for char in word))
			toAdd = dict()
			for prevW in cands:
				if prevW & currW == 0:
					toAdd[prevW + currW] = cands[prevW] + len(word)
			cands.update(toAdd)
		return max(cands.values())


class Solution:

	def maxLength(self, arr: List[str]) -> int:

		def unique_char_count(s):
			chars = set()
			for char in s:
				if char in chars:
					return -1
				else:
					chars.add(char)
			return len(s)

		def max_unique(arr, index, cur_str, result):
			if index >= len(arr):
				if unique_char_count(cur_str) > result[0]:
					result[0] = len(cur_str)
				return
			max_unique(arr, index + 1, cur_str + arr[index], result)
			max_unique(arr, index + 1, cur_str, result)
		result = [0]
		max_unique(arr, 0, '', result)
		return result[0]


class Solution:

	def maxLength(self, arr: List[str]) -> int:

		def helper(arr, substring, i):
			unique_length = len(set(substring))
			if len(substring) == unique_length:
				self.max_len = max(self.max_len, unique_length)
			if i == len(arr) - 1:
				return
			for j in range(i + 1, len(arr)):
				helper(arr, substring + arr[j], j)
			return
		self.max_len = 0
		helper(arr, '', -1)
		return self.max_len


class Solution:

	def maxLength(self, arr):

		def isValid(chars):
			if len(chars) == len(set(chars)):
				return True
			else:
				return False
		result = 0
		currentSubset = set()

		def iterate(idx):
			nonlocal result, currentSubset
			if idx == len(arr):
				candidateSolution = ''.join(currentSubset)
				if isValid(candidateSolution) and len(candidateSolution) > result:
					result = len(candidateSolution)
				return
			currentSubset.add(arr[idx])
			iterate(idx + 1)
			currentSubset.remove(arr[idx])
			iterate(idx + 1)
		iterate(0)
		return result


def bo(i):
	return ord(i) - ord('a')

class Solution:

	def maxLength(self, arr: List[str]) -> int:
		n = len(arr)
		freq = []
		ans = 0
		for i in range(n):
			s1 = set()
			for j in arr[i]:
				s1.add(bo(j))
			if len(s1) == len(arr[i]):
				freq.append(s1)
		n = len(freq)
		for i in range(1 << n):
			s = set()
			cnt = 0
			for j in range(n):
				if i & 1 << j:
					for k in freq[j]:
						s.add(k)
					cnt += len(freq[j])
					if cnt != len(s):
						break
			if cnt == len(s):
				ans = max(ans, cnt)
			if ans == 26:
				break
		return ans


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		dp = [set()]
		length = 0
		for word in arr:
			if len(word) != len(set(word)):
				continue
			curr = set(word)
			for used in dp[:]:
				if not len(used & curr):
					dp.append(used | curr)
					length = max(length, len(used | curr))
		return length


class Solution:

	def maxLength(self, arr: List[str]) -> int:

		def valid(s, baskets):
			return all([c not in baskets for c in s])

		def find_max_len_recursive(baskets, currIdx):
			if currIdx == len(arr):
				return len(baskets)
			res1 = float('-inf')
			if valid(arr[currIdx], baskets):
				res1 = find_max_len_recursive(baskets.union(set(arr[currIdx])), currIdx + 1)
			res2 = find_max_len_recursive(baskets, currIdx + 1)
			return max(res1, res2)
		arr = [s for s in arr if len(s) == len(set(s))]
		return find_max_len_recursive(set(), 0)


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		combinations = [set()]
		for a in arr:
			chars = set(a)
			if len(chars) != len(a):
				continue
			for c in combinations:
				if len(chars.intersection(c)) == 0:
					combinations.append(chars.union(c))
		return max([len(c) for c in combinations])


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		arr.sort()
		self.arr = arr
		self.tmp = []
		self.mlen = 0
		self.len = 0
		self.backtrack(0)
		return self.mlen

	def backtrack(self, pos):
		if pos == len(self.arr):
			if self.len > self.mlen:
				self.mlen = self.len
			return
		self.backtrack(pos + 1)
		lb = len(self.tmp)
		self.tmp = self.tmp + list(self.arr[pos])
		l = len(self.arr[pos])
		if l == len(self.arr[pos]) and lb + l == len(set(self.tmp)):
			self.len += l
			self.backtrack(pos + 1)
			self.len -= l
		self.tmp = self.tmp[:-l]


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		dp = [set()]
		for word in arr:
			if len(word) != len(set(word)):
				continue
			curWord = set(word)
			for used in dp[:]:
				if len(used & curWord) == 0:
					dp.append(used | curWord)
		return len(max(dp, key=len))


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		arr.sort()
		self.arr = arr
		self.tmp = []
		self.mlen = 0
		self.len = 0
		self.backtrack(0)
		return self.mlen

	def backtrack(self, pos):
		if pos == len(self.arr):
			if self.len > self.mlen:
				self.mlen = self.len
			return
		self.backtrack(pos + 1)
		lb = len(self.tmp)
		self.tmp = self.tmp + list(self.arr[pos])
		l = len(self.arr[pos])
		if l == len(self.arr[pos]) and lb + l == len(set(self.tmp)):
			self.len += l
			self.backtrack(pos + 1)
			self.len -= l
		for i in range(l):
			self.tmp.pop()


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		N = len(arr)
		charSets = [set()]
		for s in arr:
			currSet = set(s)
			if len(currSet) != len(s):
				continue
			currSize = len(charSets)
			for idx in range(currSize):
				charSet = charSets[idx]
				if charSet & currSet:
					continue
				charSets.append(charSet | currSet)
		return max((len(charSet) for charSet in charSets))


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		d = ['']
		for a in arr:
			if len(set(a)) < len(a):
				continue
			else:
				for x in d:
					if set(x) & set(a):
						continue
					else:
						t = set(a) | set(x)
						d.append(t)
		max = 0
		for i in d:
			if len(i) > max:
				max = len(i)
		return max


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		res = 0
		unique = ['']

		def isvalid(s):
			return len(s) == len(set(s))
		for word in arr:
			for u in unique:
				tmp = word + u
				if isvalid(tmp):
					unique.append(tmp)
					res = max(res, len(tmp))
		return res


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		if len(arr) == 1:
			return len(arr[0])
		self.res = 0

		def backtrack(start: int, path: set):
			self.res = max(self.res, len(path))
			if start == len(arr):
				return
			for i in range(start, len(arr)):
				new_chars = set(arr[i])
				if len(new_chars) != len(arr[i]):
					continue
				if len(new_chars & path) == 0:
					new_path = new_chars | path
					backtrack(i + 1, new_path)
		backtrack(0, set())
		return self.res


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		arr = [w for w in arr if len(w) == len(set(w))]
		hm = {}
		res = 0
		dp = {0: 0}
		for (i, w) in enumerate(arr):
			bitmask = 0
			for c in set(w):
				bit_set = 1 << ord(c) - ord('a')
				bitmask ^= bit_set
			hm[i] = bitmask
		for i in range(len(arr)):
			for p in list(dp.keys()):
				if not hm[i] & p:
					now = hm[i] ^ p
					dp[now] = max(dp.get(now, 0), dp[p] + len(arr[i]))
		return max(dp.values())


class Solution:

	def maxLength(self, l: List[str]) -> int:
		selected = set()

		def ok(word, s) -> bool:
			return not any((v in s for v in word)) and len(word) == len(set(word))

		def backTrack(l: List[str], curr_index: int, selected: set) -> int:
			maxLength = 0
			if curr_index != -1:
				for v in l[curr_index]:
					selected.add(v)
			for i in range(curr_index + 1, len(l)):
				if ok(l[i], selected):
					maxLength = max(maxLength, len(l[i]) + backTrack(l, i, selected.copy()))
			return maxLength
		return backTrack(l, -1, selected)


class Solution:

	def maxLength(self, arr: List[str]) -> int:

		def dfs(start, seen):
			nonlocal res
			if start == len(arr):
				res = max(res, sum((len(arr[i]) for i in seen)))
			else:
				is_end = True
				for i in graph[start]:
					if all((len(arr[j].intersection(arr[i])) == 0 for j in seen)):
						is_end = False
						seen.append(i)
						dfs(i, seen)
						seen.pop()
				if is_end:
					res = max(res, sum((len(arr[i]) for i in seen)))
		arr = [item for item in arr if len(item) == len(set(item))]
		arr = list(map(set, arr))
		graph = collections.defaultdict(list)
		for i in range(len(arr)):
			for j in range(i + 1, len(arr)):
				if len(arr[i].intersection(arr[j])) == 0:
					graph[i].append(j)
		print(dict(graph))
		res = 0
		for i in range(len(arr)):
			dfs(i, [i])
		return res


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		myQueue = collections.deque([('', 0)])
		maxLen = 0
		while myQueue:
			(word, start) = myQueue.popleft()
			for i in range(start, len(arr)):
				newWord = word + arr[i]
				if self.isUnique(newWord):
					maxLen = max(maxLen, len(newWord))
					myQueue.append((newWord, i + 1))
		return maxLen

	def isUnique(self, s):
		return len(s) == len(set(s))


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		self.array = arr
		return max(self.recurse('', set(), 0, True), self.recurse('', set(), 0, False))

	def recurse(self, prefix: str, letters: set, index: int, include: bool):
		if index >= len(self.array):
			return len(prefix)
		if include:
			if len(self.array[index]) != len(set(self.array[index])):
				return len(prefix)
			if any((letter in letters for letter in self.array[index])):
				return len(prefix)
			return max(self.recurse(''.join((prefix, self.array[index])), letters | set(self.array[index]), index + 1, True), self.recurse(''.join((prefix, self.array[index])), letters | set(self.array[index]), index + 1, False))
		return max(self.recurse(prefix, letters, index + 1, True), self.recurse(prefix, letters, index + 1, False))


class Solution:

	def is_unique(self, word):
		letters = set()
		for letter in word:
			if letter in letters:
				return False
			letters.add(letter)
		return True

	def maxLength(self, arr: List[str]) -> int:
		uniques = set()
		for piece in arr:
			next_uniques = set()
			for unique in uniques:
				concat = piece + unique
				if self.is_unique(concat):
					next_uniques.add(concat)
			if self.is_unique(piece):
				next_uniques.add(piece)
			for u in next_uniques:
				uniques.add(u)
		if uniques:
			return max([len(x) for x in uniques])
		return 0


from collections import Counter

class Solution:

	def maxLength(self, arr) -> int:
		if len(arr) == 1:
			return len(arr[0])
		self.max_val = 0
		max_val = float('-inf')

		def check(string):
			c = Counter(string)
			for (key, val) in c.items():
				if c[key] > 1:
					return False
			return True

		def _helper(string, index):
			if check(string):
				self.max_val = max(self.max_val, len(string))
			else:
				return
			if index >= len(arr):
				return
			for i in range(index, len(arr)):
				newString = string + arr[i]
				_helper(newString, i + 1)
		print(_helper('', 0))
		return self.max_val


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		if not arr:
			return 0
		max_length = 0
		duplicates = set([])
		from collections import deque
		queue = deque([])
		for (idx, val) in enumerate(arr):
			if val in duplicates or self.doesDuplicateExist(val):
				continue
			queue.appendleft((idx, val, len(val)))
			duplicates.add(val)
		n = len(arr)
		while len(queue) != 0:
			(idx, curr, curr_len) = queue.pop()
			max_length = max(max_length, curr_len)
			for i in range(idx + 1, n):
				newWord = curr + arr[i]
				if newWord in duplicates or self.doesDuplicateExist(newWord):
					continue
				queue.appendleft((i, newWord, len(newWord)))
				duplicates.add(newWord)
		return max_length

	def doesDuplicateExist(self, val):
		dup = set()
		for char in val:
			if char in dup:
				return True
			dup.add(char)
		return False


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		self.res = 0

		def walk(i, temp):
			self.res = max(self.res, len(temp))
			for j in range(i, len(arr)):
				if all((v <= 1 for v in list(collections.Counter(temp + arr[j]).values()))):
					walk(j + 1, temp + arr[j])
		walk(0, '')
		return self.res


class Solution:

	def maxLength(self, arr) -> int:
		maxLen = 0
		arr = sorted(arr, key=lambda x: len(x), reverse=True)
		self.compatible = {}
		for i in range(len(arr)):
			currString = arr[i]
			if self.noDupes(currString):
				if currString not in self.compatible:
					self.compatible[currString] = []
				for j in range(i + 1, len(arr)):
					if self.noDupes(arr[j]) and self.uniqueChars(currString, arr[j]):
						self.compatible[currString].append(arr[j])
		for key in self.compatible:
			if len(self.compatible[key]) == 0:
				length = len(key)
			else:
				length = self.findLength(key, key, 0)
			maxLen = max(maxLen, length)
		return maxLen

	def uniqueChars(self, s1, s2):
		for c in s2:
			if c in s1:
				return False
		return True

	def noDupes(self, string):
		counts = {}
		for c in string:
			counts[c] = counts.get(c, 0) + 1
			if counts[c] > 1:
				return False
		return True

	def findLength(self, currString, totalString, maxLen):
		for string in self.compatible[currString]:
			if self.uniqueChars(totalString, string):
				maxLen = max(maxLen, self.findLength(string, totalString + string, len(totalString) + len(string)))
		return maxLen


class Solution:

	def __init__(self):
		self._maxLength = 0

	def maxLength(self, arr: List[str]) -> int:
		self.uniqueLengths(arr, [])
		return self._maxLength

	def uniqueLengths(self, arr, concat):
		result = ''.join(concat)
		if not self.hasUniqueChars(result):
			return
		self._maxLength = max(self._maxLength, len(result))
		for i in range(len(arr)):
			concat.append(arr[i])
			self.uniqueLengths(arr[i + 1:], concat)
			concat.pop()

	def hasUniqueChars(self, concat):
		counter = Counter(concat)
		return all([x == 1 for x in counter.values()])


from collections import Counter

class Solution:

	def maxLength(self, arr: List[str]) -> int:
		max_str = 0
		for i in range(len(arr)):
			if self.is_unique(arr[i]) and len(arr[i]) > max_str:
				max_str = len(arr[i])
			concat = [arr[i]]
			for j in range(i + 1, len(arr)):
				for x in concat:
					c = x + arr[j]
					if self.is_unique(c):
						if len(c) > max_str:
							max_str = len(c)
						concat.append(c)
		return max_str

	def is_unique(self, str):
		for v in Counter(str).values():
			if v > 1:
				return False
		return True


class Solution(object):

	def maxLength(self, A):
		for i in range(len(A) - 1, -1, -1):
			if len(set(A[i])) != len(A[i]):
				A.pop(i)
		N = len(A)
		B = []
		for word in A:
			ct = [0] * 26
			for letter in word:
				ct[ord(letter) - ord('a')] += 1
			B.append(ct)
		self.ans = 0
		count = [0] * 26

		def search(i):
			if i == N:
				cand = sum(count)
				if cand > self.ans:
					self.ans = cand
				return
			for (letter, ct) in enumerate(B[i]):
				if ct and count[letter]:
					search(i + 1)
					break
			else:
				search(i + 1)
				for (letter, ct) in enumerate(B[i]):
					if ct:
						count[letter] += 1
				search(i + 1)
				for (letter, ct) in enumerate(B[i]):
					if ct:
						count[letter] -= 1
		search(0)
		return self.ans


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		d = {}

		def helper(banned, start):
			if start == len(arr):
				return len(banned)
			k = tuple(sorted(str(banned) + str(start)))
			if k in d:
				return d[k]
			string = arr[start]
			new_set = set()
			for i in string:
				if i in banned or i in new_set:
					return helper(banned, start + 1)
				new_set.add(i)
			new_banned = banned.union(new_set)
			val = max(helper(new_banned, start + 1), helper(banned, start + 1))
			d[k] = val
			return val
		initial_banned = set()
		res = helper(initial_banned, 0)
		return res


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		newarr = []
		for w in arr:
			if len(set(w)) == len(w):
				newarr.append(w)
		arr = newarr
		n = len(arr)
		res = 0
		str_masks = [None] * n
		for i in range(n):
			wd = arr[i]
			mask = 0
			for ch in wd:
				ch_pos = ord(ch) - ord('a')
				mask |= 1 << ch_pos
			str_masks[i] = mask

		def dfs(idx, mask, curlen):
			nonlocal res
			if idx == n:
				res = max(res, curlen)
				return
			if mask & str_masks[idx] == 0:
				dfs(idx + 1, mask | str_masks[idx], curlen + len(arr[idx]))
			dfs(idx + 1, mask, curlen)
		dfs(0, 0, 0)
		return res


from collections import defaultdict

class Solution:

	def maxLength(self, arr: List[str]) -> int:
		self.longest = 0

		def valid(s):
			d = defaultdict(int)
			for char in s:
				d[char] += 1
				if d[char] == 2:
					return False
			return True

		def backtrack(curr, ind):
			if ind == len(arr):
				if len(curr) > self.longest:
					self.longest = len(curr)
				return
			for i in range(ind, len(arr)):
				temp = curr + arr[i]
				if valid(temp):
					backtrack(curr + arr[i], i + 1)
			if len(curr) > self.longest:
				self.longest = len(curr)
			return
		for i in range(len(arr)):
			if valid(arr[i]):
				backtrack(arr[i], i)
		return self.longest


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		newarr = []
		for cur in arr:
			newarr.append(collections.Counter(cur))
		res = [0]

		def helper(cur, index):
			if index == len(arr):
				res[0] = max(res[0], len(cur))
			else:
				if len(arr[index]) == len(newarr[index]):
					if not newarr[index] & cur:
						helper(newarr[index] + cur, index + 1)
				helper(cur, index + 1)
		helper(collections.Counter(''), 0)
		return res[0]


from collections import Counter

class Solution:

	def back(self, arr, soln, solns):
		if not arr:
			solns.append([len(soln), soln])
			return solns
		for i in range(len(arr)):
			sa = set(arr[i])
			sb = set(soln)
			c = dict(Counter(arr[i]))
			if max(c.values()) == 1 and len(sb.intersection(sa)) == 0:
				solncopy = soln
				solncopy += arr[i]
				solns = self.back(arr[i + 1:], solncopy, solns)
		solns.append([len(soln), soln])
		return solns

	def maxLength(self, arr: List[str]) -> int:
		solns = []
		for i in range(len(arr)):
			soln = arr[i]
			c = dict(Counter(arr[i]))
			if max(c.values()) == 1:
				solns = self.back(arr[i + 1:], soln, solns)
		if not solns:
			return 0
		return max(solns, key=lambda x: x[0])[0]


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		letters_dict = {}

		def dfs(letter_set, arr, i):
			if i >= len(arr):
				return 0
			if (tuple(letter_set), i) not in letters_dict:
				if len(set(arr[i]).intersection(letter_set)) == 0 and len(set(arr[i])) == len(arr[i]):
					letters_dict[tuple(letter_set), i] = max(dfs(letter_set.union(set(arr[i])), arr, i + 1) + len(set(arr[i])), dfs(letter_set, arr, i + 1))
				else:
					letters_dict[tuple(letter_set), i] = dfs(letter_set, arr, i + 1)
			return letters_dict[tuple(letter_set), i]
		return dfs(set(), arr, 0)


import collections

class Solution:

	def maxLength(self, arr: List[str]) -> int:
		self.m = collections.defaultdict(list)
		for ix_1 in range(len(arr)):
			set_1 = set(list(arr[ix_1]))
			for ix_2 in range(ix_1 + 1, len(arr)):
				set_2 = set(list(arr[ix_2]))
				if len(set_1) == len(arr[ix_1]) and len(set_2) == len(arr[ix_2]) and (len(set_1.intersection(set_2)) == 0):
					self.m[ix_1].append(ix_2)
		self.ans = 0
		for ix in range(len(arr)):
			if len(set(list(arr[ix]))) == len(arr[ix]):
				self.dfs(arr, [ix])
		return self.ans

	def dfs(self, arr, visiting):
		curr = visiting[-1]
		l = [len(arr[i]) for i in visiting]
		self.ans = max(sum(l), self.ans)
		if not self.m.get(curr):
			return
		for i in self.m.get(curr):
			if i in visiting:
				continue
			possible = True
			for j in visiting[:-1]:
				if len(set(list(arr[i])).intersection(set(list(arr[j])))) > 0:
					possible = False
					break
			if possible:
				visiting.append(i)
				self.dfs(arr, visiting)
				visiting.pop()


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		if len(arr) == 1:
			if len(set(arr[0])) == len(arr[0]):
				return len(arr[0])
			else:
				return 0
		new_arr = []
		for s in arr:
			if len(s) == len(set(s)):
				new_arr.append((set(s), len(s)))
		if not new_arr:
			return 0
		ans = 0

		def backtrack(ind, temp, temp_sum):
			nonlocal ans
			if temp_sum > ans:
				ans = temp_sum
			for i in range(ind, len(new_arr)):
				if not new_arr[i][0] & temp:
					backtrack(i + 1, temp | new_arr[i][0], temp_sum + new_arr[i][1])
				else:
					backtrack(i + 1, temp, temp_sum)
		backtrack(0, set(), 0)
		return ans


from collections import Counter

class Solution:

	def maxLength(self, arr: List[str]) -> int:
		self.max_len = 0
		for (i, s) in enumerate(arr):
			self.bfs(Counter(s), arr, i)
		return self.max_len

	def bfs(self, counter, arr, _index):
		if max(counter.values()) > 1:
			return
		if len(counter) > self.max_len:
			self.max_len = len(counter)
		for i in range(_index + 1, len(arr)):
			s = arr[i]
			counter_copy = copy.copy(counter)
			counter_copy.update(Counter(s))
			self.bfs(counter_copy, arr, i)


class Solution:

	def maxLength(self, arr: List[str]) -> int:
		res = 0
		arr = list([x for x in arr if len(set(x)) == len(x)])
		arr = [set(x) for x in arr]

		def dfs(n, s, l, cur):
			nonlocal res
			if n == l:
				res = max(res, len(cur))
				return
			for i in range(s, len(arr)):
				if len(cur.intersection(arr[i])) == 0:
					dfs(n, i + 1, l + 1, cur.union(arr[i]))
		for i in range(len(arr) + 1):
			dfs(i, 0, 0, set())
		return res