/**
1. 类似于求全排列, dfs遍历所有可能, n=16, 复杂度为: 2^16 = 65536

2. 过滤所有不可能的字符后深搜
2.1 搜索顺序: 每个s, 都有选和不选两种可能
2.2 搜索状态: local: index, nowStatus, len , used| global: res, arr, arrStatus
2.3 剪枝: 
*/

class Solution {
    int res = 0;
    public int maxLength(List<String> arr) {
        int n = arr.size();
        List<String> list = new ArrayList<>();

        int[] status = new int[n];
        for (int i = 0 ; i < n; i++){
            String s = arr.get(i);
            status[list.size()] = getStatus(s);
            if (status[list.size()] == -1) continue;
            list.add(s);
        }
        n = list.size();
        res = 0;
        dfs(0, 0, 0, 0, list, status);
        return res;
    }

    private void dfs(int index, int now, int used, int len,  List<String> list, int[] status){
        if (index >= list.size()) return;
        dfs(index + 1, now, used, len, list, status); 

        if (((status[index] & now) == 0) && (((used >> index) & 1) == 0)){
            now |= status[index];
            used |= 1 << index;
            len += list.get(index).length();
            res = Math.max(res, len);
            dfs(index + 1, now, used, len, list, status);     
        }
    }

    private int getStatus(String s){
        int res = 0;
        for (int i = 0 ; i < s.length(); i++){
            int index =(s.charAt(i) - 'a');
            if (((res >> index) & 1) == 1 ) return -1;
            res |= 1 << index;
            // System.out.printf("i:%d, index:%d, res:%d, \n", i, index, res);
        }
        return res;
    }    
}

/** (error!)
0. 本题无法用DP来做, DP要满足"无后效性" + "最优子结构",  本题不符合 "最优子结构"
=====

1. 状态定义: f[i]为 处理arr[0 ... i] 后的最大长度
2. 状态计算: 以最后一个位置i 划分为:
2.1 i独立: f[i]
2.2 用i接到前面:    f[i] = MAX(f[0 ... i-1] + arr[i])
3. 边界: f[i] = arr[i].length()
*/


// class Solution {
//     public int maxLength(List<String> arr) {
//         int n = arr.size();
//         List<String> list = new ArrayList<>();

//         int[] f = new int[n];
//         int[] fs = new int[n];
//         int[] as = new int[n];
//         for (int i = 0 ; i < n; i++){
//             String s = arr.get(i);
//             int status = getStatus(s);
//             if (status == -1) continue;
//             list.add(s);
//             int index = list.size()-1;
//             as[index] = status;
//             fs[index] = status;
//             f[index] = s.length();
//         }

//         n = list.size();

//         for (int i = 1 ; i < n ; i++){
//             int len = list.get(i).length();
//             for (int j = 0; j < i; j++){
//                 if ((fs[j] & as[i]) == 0 && f[i] < f[j] + len){
//                     fs[i] = fs[j] | as[i];
//                     f[i] = f[j] + len;
//                 }
//                 int single = list.get(j).length();
//                 if ((as[j] & as[i]) == 0 && f[i] < single + len){
//                     fs[i] = as[j] | as[i];
//                     f[i] = single + len;
//                 }
//             }
//         }
//         return Arrays.stream(f).max().getAsInt();
//     }

//     private int getStatus(String s){
//         int res = 0;
//         for (int i = 0 ; i < s.length(); i++){
//             int index =(s.charAt(i) - 'a');
//             if (((res >> index) & 1) == 1 ) return -1;
//             res |= 1 << index;
//             // System.out.printf("i:%d, index:%d, res:%d, \n", i, index, res);
//         }
//         return res;
//     }
// }