<p>You are given an array of strings <code>arr</code>. A string <code>s</code> is formed by the <strong>concatenation</strong> of a <strong>subsequence</strong> of <code>arr</code> that has <strong>unique characters</strong>.</p>

<p>Return <em>the <strong>maximum</strong> possible length</em> of <code>s</code>.</p>

<p>A <strong>subsequence</strong> is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [&quot;un&quot;,&quot;iq&quot;,&quot;ue&quot;]
<strong>Output:</strong> 4
<strong>Explanation:</strong> All the valid concatenations are:
- &quot;&quot;
- &quot;un&quot;
- &quot;iq&quot;
- &quot;ue&quot;
- &quot;uniq&quot; (&quot;un&quot; + &quot;iq&quot;)
- &quot;ique&quot; (&quot;iq&quot; + &quot;ue&quot;)
Maximum length is 4.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [&quot;cha&quot;,&quot;r&quot;,&quot;act&quot;,&quot;ers&quot;]
<strong>Output:</strong> 6
<strong>Explanation:</strong> Possible longest valid concatenations are &quot;chaers&quot; (&quot;cha&quot; + &quot;ers&quot;) and &quot;acters&quot; (&quot;act&quot; + &quot;ers&quot;).
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> arr = [&quot;abcdefghijklmnopqrstuvwxyz&quot;]
<strong>Output:</strong> 26
<strong>Explanation:</strong> The only string in arr has all 26 characters.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= arr.length &lt;= 16</code></li>
	<li><code>1 &lt;= arr[i].length &lt;= 26</code></li>
	<li><code>arr[i]</code> contains only lowercase English letters.</li>
</ul>

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
        # we make list of sets of char of each strs
        arrset = []
        for i in range(len(arr)):
            if len(set(arr[i])) == len(arr[i]):
                arrset.append((set(arr[i]), len(arr[i])))
        queue = []
        maxLen = 0
        for i in range(len(arrset)-1):
            queue.append((arrset[i][0], arrset[i][1], arrset[i+1:]))
            if maxLen < arrset[i][1]:
                maxLen = arrset[i][1]
        if 0 < len(arrset) and maxLen < arrset[len(arrset)-1][1]:
            maxLen = arrset[len(arrset)-1][1]
        while 0 < len(queue):
            t = queue.pop(0)
            concat, length, available = t[0], t[1], t[2]
            for i in range(len(available)):
                if self.disjoint(concat, available[i][0]):
                    newConcat = concat.copy() | available[i][0].copy()
                    newLength = length + available[i][1]
                    newAvailable = available[i+1:]
                    if 0 < len(newAvailable):
                        queue.append((newConcat, newLength, newAvailable))
                    else:
                        if maxLen < newLength:
                            maxLen = newLength
                else:
                    if maxLen < length:
                        maxLen = length
        return maxLen

    def disjoint(self, set1, set2):
        for key in set2:
            if key in set1:
                return False
        return True
        
21800