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: interview

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
            # print(arr[i])
            for c in arr[i]:
                if c in chars:
                    isGood = False
                    break
            if isGood:
                # print(arr[i], \"is good\")
                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)
            # else:
                # print(arr[i], \"is bad\")
        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)

# print(Solution().maxLength([\"un\",\"iq\",\"ue\"]))


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))
        #print(uniqELements)
        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):
            # print(\"Bitlist: {a}, Index: {b}\".format(a=bitlist, b=index))
            if index == len(arr):
                # print(\"returning length\")
                return len(buildSet(bitlist))
            
            new_bitlist = bitlist[:]
            new_bitlist[index] = 0
            # print(\"recursing with not included\")
            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:
                # print(\"return max of both\")
                
                new_bitlist[index] = 1
                return max(not_included, recurse(new_bitlist, index+1))
        
        return recurse([0 for _ in arr], 0)
            
            
            
        # [0, 1, 1, 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 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)

        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:
        
        # setify
        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):
                    # print(t)
                    arr.append(t)
                    maxVal = max(maxVal, len(val))
        # print(dct)
        return maxVal

class Solution:   
    
    def maxLength(self, arr: List[str]) -> int:
       
        #pre strip dupes 
        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
        
        #dfs
        #       incl
        # not inc    incl
        
        
        def recurse(bitlist, index):
            if index == len(arr):
                return len(buildSet(bitlist))
            
            new_bitlist = bitlist[:]
            
            #index is our depth of the tree
            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 maxLength(self, arr: List[str]) -> int:
        #array with all possible unique string combinations so far

        possible_strings = ['']
        maximum = 0
        for i in range(len(arr)):
            temp_len = len(possible_strings)
            for j in range(temp_len):
                #trying combination
                x = arr[i] + possible_strings[j]
                #string is unique
                if (len(x)==len(set(x))):
                    #append to possible strings
                    possible_strings.append(x)
                    #set max
                    maximum = max(maximum,len(x))
        return maximum



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:
        
        # N is length of arr, K is longest str item in arr
        
        # filter and setify O(NK) time and space
        new_arr = []
        for string in arr:
            string_set = set(string)
            if len(string_set) == len(string):
                new_arr.append(string_set)
        arr = new_arr
        
        # recursive build O(?) with visited O(?) space
        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
        # print(self.visited)
        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 = {}   # ind: dict
        new_ind = 0
        for i in range(len(arr)):
            ind_dic[i] = Counter(arr[i])
        while st:
            #print(st)
            sub,ind = st.pop(0)
            if sub: l = max(l,len(sub))
            if ind >= len(arr): continue
            if not sub: # first word
                st.append((None,ind + 1))
                if len(arr[ind]) == len(set(arr[ind])): st.append((arr[ind],ind+1))
            else: 
                cur_dic = Counter(sub)
                #print(cur_dic.keys())
                #print(ind_dic[ind].keys())
                #print(set(cur_dic.keys()).intersection(set(ind_dic[ind].keys())))
                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: # no common char
                    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]:
    #     print(uniqueLength(curr_string))
        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:
        
        # setify O(N*M)
        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):

            # start with unique elements in given list
            dp = [set(x) for x in arr if len(set(x)) == len(x)]

            for v in arr:
                # check for duplicates
                if len(a := set(v)) == len(v):
                    # concat to each valid set in list
                    for b in dp:
                        # skip if sets share letters
                        if a & b:
                            continue
                        # combine sets, add to dp
                        dp.append(a | b)
            # remove initial sets because we need to concatenate
            #for x in arr: 
            #    if (tmp := set(x)) in dp:
            #       dp.remove(tmp)
            # make sure we have valid answer
            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)
        # print(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)
        
        
        # Get filter out bad input.
        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:
  # I believe this problem is equivalent to SAT with weighted variables so I
  # won't try to beat exp complexity. The state space is 2^16 configurations
  # large so exp complexity shouldn't be a problem.

  def maxLength(self, arr):
    # From python docs: https://docs.python.org/3/library/itertools.html#itertools-recipes
    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:
                    # print(string)
                    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)

# https://www.youtube.com/watch?v=N7womGmLXh8
# https://www.youtube.com/watch?v=pD3cHFNyW2I
class Solution:
    # backtracking
    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)  # use arr[i]
            dfs(i + 1, s + candi[i])  # without using arr[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:
        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([c for c in 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:
    def maxLength(self, arr: List[str]) -> int:
        
        self.output = []
        self.res = 0
        
        self.dfs(arr)
        # print(self.output)
        # print(self.res)
        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)
        # print(st)

        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:
        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([c for c in 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(set(curr), arr, i+1))
            
        return max_len

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
            
            
        


# https://www.youtube.com/watch?v=N7womGmLXh8
# https://www.youtube.com/watch?v=pD3cHFNyW2I
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:
        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)
                # temp = 
                # for c in arr[idx]:
                #     chars.append(c)
                helper(idx + 1, chars + list(arr[idx]))
                        
                        
                    
        helper(0, [])
        return self.max
            
            
        


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:
        if not arr: return 0
        def isUnique(s): return len(set(s)) == len(s)
        def dfs(arr, res, curr):
            yield curr
            for i in range(len(arr)):
                yield from dfs(arr[i + 1:], res, curr + arr[i])
        res = 0
        for st in dfs(arr, res, ''):
            if isUnique(st):
                res = max(res, len(st))
        return res

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:
            
        # backtracking function
        
        def helper(arr, substring, i):
            
            # get the length of the substring without char duplication 
            unique_length = len(set(substring))
            
            # if there is no duplicate chars
            if len(substring) == unique_length:
                self.max_len = max(self.max_len, unique_length)
            
            # check if we reached the last substring in arr
            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:
  # I believe this problem is equivalent to SAT with weighted variables so I
  # won't try to beat exp complexity. The state space is 2^16 configurations
  # large so exp complexity shouldn't be a problem.

  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):
        # print(self.tmp,self.len)
        if pos == len(self.arr):
            
            if self.len > self.mlen:
                # print(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()
        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):
        # print(self.tmp,self.len)
        if pos == len(self.arr):
            
            if self.len > self.mlen:
                # print(self.len,self.mlen)
                self.mlen = self.len
            return
        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()
        self.tmp = self.tmp[:-l]
        self.backtrack(pos+1)
        
        


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):
        # print(self.tmp,self.len)
        if pos == len(self.arr):
            
            if self.len > self.mlen:
                # print(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()
        # self.tmp = self.tmp[:-l]
        
        
        


class Solution:
    def maxLength(self, arr: List[str]) -> int:
        N = len(arr)
        # store the intermediate sets of unique characters
        charSets = [set()]
        # iterate over each string
        for s in arr:
            # iterate over each char set to see if we can add the chars in s into it
            currSet = set(s)
            # skip string swith duplicate chars
            if len(currSet) != len(s):
                continue
            currSize = len(charSets)
            for idx in range(currSize):
                charSet = charSets[idx]
                # check if the sets have an intersection (duplicate chars)
                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:
    # https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/discuss/631245/Python-3-Easy-Code-Intutive-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:
        maxlen = 0
        unique = ['']

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

        for word in arr:
            for j in unique:
                tmp = word + j
                if isvalid(tmp):
                    unique.append(tmp)
                    maxlen = max(maxlen, len(tmp))

        return maxlen

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:
                    # we can concat 
                    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]: # add the chosen word to selected
                    selected.add(v)
            
            for i in range(curr_index+1,len(l)):
                if ok(l[i],selected): # word is good - so we choose it
                    
                    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
            


#https://wentao-shao.gitbook.io/leetcode/graph-search/1239.maximum-length-of-a-concatenated-string-with-unique-characters

class Solution:
    def maxLength1(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)
            
        res = 0
        for i in range(len(arr)):
            dfs(i, [i])
        return res
            
    def maxLength(self, arr: List[str]) -> int:
        
        def dfs(seen):
            nonlocal res
            is_end = True
            for i in graph[seen[-1]]:
                if all(len(arr[j].intersection(arr[i]))==0 for j in seen):
                    is_end = False
                    seen.append(i)
                    dfs(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)
            
        res = 0
        for i in range(len(arr)):
            dfs([i])
        return res
            


class Solution:
    def maxLength(self, arr: List[str]) -> int:
        myQueue = collections.deque([('', 0)]) # word, index to start search from
        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):
        # Base case
        if index >= len(self.array):
            return len(prefix)
        
        # Recursive cases
        if include:
            # Do not include a string that has duplicate characters within itself
            if len(self.array[index]) != len(set(self.array[index])):
                return len(prefix)
            
            # Do not include a string that contains letters already in 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:
            # print(piece)
            next_uniques = set()
            for unique in uniques:
                concat = piece + unique
                # print(\"{0}: {1}\".format(concat, self.is_unique(concat)))
                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.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):
        # Base case
        if index >= len(self.array):
            return len(prefix)
        
        # Recursive case
        if include and len(self.array[index]) == len(set(self.array[index])):
            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 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:
    
    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)):
            if self.is_unique(arr[i]):
                v = frozenset(arr[i])

                dct[v] = len(v)
                maxVal = max(maxVal, len(v))
                
            for j in range(i+1, len(arr)):
                t = arr[i] + arr[j]
                val = frozenset(t)
                
                if val not in dct.keys():
                    if self.is_unique(t):
                        # print(t)
                        arr.append(t)
                        dct[val] = len(val)
                        maxVal = max(maxVal, len(val))
        print(dct)
        return maxVal

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):
        if not self.hasUniqueChars(''.join(concat)):
            return
        
        self._maxLength = max(self._maxLength, len(''.join(concat)))
        
        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()])

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
            # use arr[idx]
            if mask & str_masks[idx] == 0:
                # can use arr[idx]
                dfs(idx + 1, mask | str_masks[idx], curlen + len(arr[idx]))
            # not use 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]

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]) and 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):
        # print(\"Arr {} | Soln {}\".format(arr, soln))
        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)
        # print(solns)
        # for s in solns:
            # print(s)
        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)

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))
            
            not_included = recurse(bitlist, index+1)
            
            if len(arr_sets[index]) != len(arr[index]) or buildSet(bitlist).intersection(arr_sets[index]):
                return not_included
            else:
                
                new_bitlist = bitlist[:]
                new_bitlist[index] = 1
                return max(not_included, recurse(new_bitlist, index+1))
        
        return recurse([0 for _ in arr], 0)


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])
            return
        
        walk(0, '')
        return self.res
            


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.m[ix_2].append(ix_1)
                    
        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:
        #array with all possible unique string combinations so far
        possible_strings = ['']
        maximum = 0
        for i in range(len(arr)):
            temp_len = len(possible_strings)
            for j in range(temp_len):
                #trying combination
                x = arr[i] + possible_strings[j]
                #string is unique
                if (len(x)==len(set(x))):
                    #append to possible strings
                    possible_strings.append(x)
                    #set max
                    maximum = max(maximum,len(x))
        return maximum



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)):
            if self.is_unique(arr[i]):
                maxVal = max(maxVal, len(arr[i]))
                
            for j in range(i+1, len(arr)):
                t = arr[i] + arr[j]
                
                if self.is_unique(t):
                    arr.append(t)
                    maxVal = max(maxVal, len(t))
        # print(dct)
        return maxVal

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
        # print(new_arr)
        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

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)):
            if self.is_unique(arr[i]):
                maxVal = max(maxVal, len(arr[i]))
                
            for j in range(i+1, len(arr)):
                t = arr[i] + arr[j]
                
                if self.is_unique(t):
                    # print(t)
                    arr.append(t)
                    maxVal = max(maxVal, len(t))
        # print(dct)
        return maxVal

class Solution:
    
    def is_unique(self, s):
        return len(set(s)) == len(s)
    
    def maxLength(self, arr: List[str]) -> int:
        maxVal = 0
        
        for i in range(0, len(arr)):
            if self.is_unique(arr[i]):
                maxVal = max(maxVal, len(arr[i]))
                
            for j in range(i+1, len(arr)):
                t = arr[i] + arr[j]
                
                if self.is_unique(t):
                    arr.append(t)
                    maxVal = max(maxVal, len(t))
        # print(dct)
        return maxVal

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]))
                # new_cur = cur + arr[i]
                # if len(set(new_cur)) != len(new_cur):
                #     return
                # dfs(n, i+1, l+1, new_cur)
        for i in range(len(arr)+1):
            dfs(i, 0, 0, set())
        return res