You are given an array of strings arr. A string s is formed by the concatenation of a subsequence of arr that has unique characters.

Return the maximum possible length of s.

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

&nbsp;
Example 1:

Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All the valid concatenations are:
- ""
- "un"
- "iq"
- "ue"
- "uniq" ("un" + "iq")
- "ique" ("iq" + "ue")
Maximum length is 4.


Example 2:

Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible longest valid concatenations are "chaers" ("cha" + "ers") and "acters" ("act" + "ers").


Example 3:

Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26
Explanation: The only string in arr has all 26 characters.


&nbsp;
Constraints:


	1 &lt;= arr.length &lt;= 16
	1 &lt;= arr[i].length &lt;= 26
	arr[i] contains only lowercase English letters.


class Solution:
    def maxLength(self, arr: List[str]) -> int:
        ans = 0
        count = [0]*26
        counts = []
        new_arr = []

        for string in arr:
            flag = True
            tmp = [0]*26
            for ch in string:
                if tmp[ord(ch) - 97] == True:
                    flag = False
                    break
                else:
                    tmp[ord(ch) - 97] = True

            if flag == False:continue
            counts.append(tmp)
            new_arr.append(string)

        n = len(new_arr)

        def compatible(a,b):
            for i in range(26):
                if a[i] == True and b[i] == True: return False
            return True

        def addUp(a,b):
            for i in range(26):
                if b[i] == True: a[i] = True

        def solve(index,count):
            if index == n:return 0
            cpy = count.copy()
            ch1 = -inf
            if compatible(count,counts[index]):
                addUp(count,counts[index])
                ch1 = solve(index+1,count) + len(new_arr[index])
            ch2 = solve(index+1 , cpy)
            ans = max(ch1,ch2)
            return ans

        return solve(0,count)
class Solution {
    public int maxLength(List<String> arr) {
        String[] words = arr.stream().filter(o -> o.chars().distinct().count() == o.length()).toArray(String[]::new);
        int[] dp = new int[1<<words.length];
        int[] ok = new int[1<<words.length];
        for (int i = 0; i < words.length; i++){
            for (char ch : words[i].toCharArray()){
                ok[1<<i]|=1<<(ch-'a');
                dp[1<<i]++;
            }
        }
        int ans = 0;
        for (int i = 0; i < dp.length; i++){
            if ((ok[i&(i-1)]&ok[i&-i])==0){
                dp[i] = dp[i&(i-1)] + dp[i&-i];
                ok[i] = ok[i&(i-1)] | ok[i&-i];
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}
/*
1. Create a integer vector, where each integer's bits represent, if a particular char is present or not
2. Loop each word in the array and set each bit, create bit map of each word
3. Use recursion to add each word with take once and not to take once type dp recursion 
4. A word can only be taken if its bits are not overlaping with the current string's bit status
   - to do this, we need to check if there sum is equal to bit wise andding of them, 
     if eaual then there is no overlaping, if not equal then there is overlaping
5. Also we don't have to take the word which has repeted char ( if we have set it to INT_MAX )
6. Finally if i is less then 0, check the size of the s with the ans and take maximum
*/

class Solution {
public:
    int ans = 0;
    void solve(vector<int>& v, vector<string>& arr, int i, string s, int status){
        if(i < 0) { 
            ans = max(ans, (int)s.size());
        }else{
            solve(v, arr, i-1, s, status);
            if( (v[i] != INT_MAX ) && ( (v[i] + status) == (v[i] | status)) ){ 
                solve(v, arr, i-1, s+arr[i], status  | v[i]);
            }
        }
    }
    
    int maxLength(vector<string>& arr) {
        vector<int> v(arr.size());
        for(int i= 0; i < arr.size(); ++i){
            for(auto c: arr[i]) {
                if((v[i] >> (c - 'a'))& 1){ //if already bit is set, then set value to INT_MAX
                    v[i] = INT_MAX;
                }else{                      // if not set, then set it to 1
                    v[i] = v[i] | (1 << (c - 'a'));
                }
            }
        }
        string s = "";
        solve(v, arr, arr.size()-1, s, 0);
        return ans;
    }
};
var maxLength = function(arr) {
    const bits = [];
    for(let word of arr) {
        let b = 0, flag = true;
        for(let c of word) {
            const idx = c.charCodeAt(0) - 'a'.charCodeAt(0);
            const setBit = (1 << idx);
            if((b & setBit) != 0) {
                flag = false;
                break;
            }
            b = (b ^ setBit);
        }
        if(flag) bits.push(b);
    }
    
    const len = bits.length;
    const dp = new Map();
    const solve = (i = 0, b = 0) => {
        if(i == len) {
            let c = 0;
            while(b > 0) {
                c += (b & 1);
                b >>= 1;
            }
            return c;
        }
        const key = [i, b].join(':');
        if(dp.has(key)) return dp.get(key);
        
        let ans = 0;
        if((b & bits[i]) == 0) {
            // take
            ans = Math.max(ans, solve(i + 1, b | bits[i]));
        }
        ans = Math.max(ans, solve(i + 1, b));
        dp.set(key, ans);
        return ans;
    }
    return solve();
};
Maximum Length of a Concatenated String with Unique Characters