题目：串联字符串的最大长度

• 给定一个字符串数组arr，字符串s是将arr 某一子序列字符串连接所得的字符串，如果s 中的每一个字符都只出现过一次，那么它就是一个可行解。
• 请返回所有可行解s中最长长度。

示例 1：

输入：arr = ["un","iq","ue"]
输出：4
解释：所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique"，最大长度为 4。

示例 2：

输入：arr = ["cha","r","act","ers"]
输出：6
解释：可能的解答有 "chaers" 和 "acters"。

示例 3：

输入：arr = ["abcdefghijklmnopqrstuvwxyz"]
输出：26

提示：

• 1 <= arr.length <= 16
• 1 <= arr[i].length <= 26
• arr[i]中只含有小写英文字母

来源：力扣（LeetCode）第1239题

链接：https://leetcode-cn.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters

分析：

• 使用位压缩和回溯就可以完成这道题。
• 每一个字符串我们有两种选择，一种是用这个字符串，另一个是不用这个字符串。
• 我们用一个int类型的整数代表字符串每一个字符的使用情况。int总共有32位，而小写字母总共有26个，因此我可以把26个字母都存在每一个位上，1代表已经使用了，0代表未使用。
• 如果用这个字符串，我们就要把当前的字符串长度加上，然后再去往下找下一个字符串。
• 如果不用这个字符串，我们不用加上当前字符串的长度，只需要找下一个字符串就行了。
• 然后比较一下两者哪个大。
• 需要注意的是，如果这个字符不能使用，就是用了会有重复的字符，那么这种情况只有一个选择，就是不用这个字符串。
• 其实这道题和dp很像，但是由于有一个状态的范围不确定，所以用dp稍有难度。

代码：

class Solution {
    int len;
    public int maxLength(List<String> arr) {
        len = arr.size();
        return dfs(arr, 0, 0);
    }

    public int dfs(List<String> arr, int index, int m) {
        if (index == len) return 0;
        int t = isJoin(arr.get(index), m);// 判断字符串是否有重复,t就是当前26个字母是否有重复，0没有，1有。
        if (t != -1) { // 一条路是用这个字符串，另一条路是不用这个字符串。比较他们谁的值更大
            return Math.max(arr.get(index).length() + dfs(arr, index + 1, t), dfs(arr, index + 1, m));
        }
        return dfs(arr, index + 1, m);// 如果有重复，那么只能选择不用这个字符串。
    }

    public int isJoin(String s, int t) {
        for (char c : s.toCharArray()) {
            int tmp = c - 'a'; // tmp的值不会超过26，因为只有小写字母。
            if ((t & (1 << tmp)) != 0) return -1;//1<<tmp意思是2的tmp次方，检查tmp位上是否是0,如果不是0说明已经有了这个字母。
            t |= (1 << tmp);//如果tmp位上是0，那么就变成1。
        }
        return t;//将当前每个字母的次数返回。
    }
}