<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 valid_state(self, state, arr): 
        string = self.get_string(state, arr)
        if len(set(string)) == len(string):
            return True
        else:
            return False

    def get_candidates(self, state, arr):
        if not state:
            return range(len(arr))
        
        string = self.get_string(state, arr)

        candidates = []
        for a in range(state[-1], len(arr)):
            new_string = string + arr[a]
            if len(set(new_string)) == len(new_string):
                candidates.append(a)
                
        return candidates

    def search(self, state, solutions, arr):
        if self.valid_state(state, arr):
            solutions.append(len(self.get_string(state, arr)))
        
        for candidate in self.get_candidates(state, arr):
            state.append(candidate)
            self.search(state, solutions, arr)
            state.pop()

    def maxLength(self, arr: List[str]) -> int:
        solutions = []
        state = []
        self.search(state, solutions, arr)
        return max(solutions)

    def get_string(self, state, arr):
        string = ''
        for i in state:
            string += arr[i]
        return string
        
176