题目描述：
Given an array of strings arr. String s is a concatenation of a sub-sequence of arr which have unique characters.
Return the maximum possible length of s.
Example 1:
Input:arr = ["un","iq","ue"]Output:4Explanation:All possible concatenations are "","un","iq","ue","uniq" and "ique".Maximum length is 4.
Example 2:
Input:arr = ["cha","r","act","ers"]Output:6Explanation:Possible solutions are "chaers" and "acters".
Example 3:
Input:arr = ["abcdefghijklmnopqrstuvwxyz"]Output:26
Constraints:
1 <= arr.length <= 16
1 <= arr[i].length <= 26
arr[i] contains only lower case English letters.
一开始的解题思路有错误：用一个26长度的array代表a-b的map，映射为character -> indexs, index为有这个字母的str的序列号，然后从第一个开始，每次先获得包括当前str在内的总长度，然后遍历当前str的每一个字符，通过字符去array里找也拥有这个字符的str，如果是第一次发现这个和当前str有重复的字符串，则把这个字符串的长度从总长度中剔除，并把它的index存入一个set，记录已经访问过这个字符串了，这样一直遍历完到当前str的最后一个字符，得到的长度就是包含当前str，且当前str为最后一个str的最长结果。但这个思路是错误的，例子：
["char", "is", "ait", "sop"]
如果按上述思路，当sop为当前str时，最后的结果是，char + ait + sop = 10，因为总长一开始是12（也就是全都加一块了），然后以sop为样本，找到is和sop有重复的s，所以剔除is。但很明显这个思路没有顾及到char和ait还有个重复的a，应该剔除ait，保留char，正确结果为7。
错解：
class Solution {
public int maxLength(List<String> arr) {
ArrayList[] m = new ArrayList[26];
int lastLength = 0;
int max = 0;
for (int i = 0; i < arr.size(); i++) {
String str = arr.get(i);
if (unique(str)) {
lastLength += str.length();
int length = lastLength;
Set<Integer> visited = new HashSet<>();
for (int j = 0; j < str.length(); j++) {
int k = str.charAt(j) - 'a';
List<Integer> indexs = m[k];
if (indexs == null) {
m[k] = new ArrayList<Integer>();
m[k].add(i);
} else {
for (Integer index : indexs) {
if (!visited.contains(index)) {
visited.add(index);
length -= arr.get(index).length();
}
}
m[k].add(i);
}
}
max = Math.max(max, length);
}
}
return max;
}
private boolean unique(String str) {
Set<Character> visited = new HashSet<>();
for (int i = 0; i < str.length(); i++) {
if (visited.contains(str.charAt(i))) return false;
visited.add(str.charAt(i));
}
return true;
}
}
正确的思路应该是dfs，持有一个set，用来记录当前已经含有的所有unique characters，每次站在当前str上时，初始set，让set只包括当前str，向前逐一回溯，对于每一个被回溯到的str，有两种选择，要它或者不要，要的话，判断能不能真的要（正在回溯到的str和已有的所有characters不重复），可以要，则把当前str的所有character加入到set中，继续下一层，回来时，从set中删掉str的所有characters，直到触底（回溯完第一个str了），计算set的size，和max比大小，最后输出max。
正解：
class Solution {
private int max = 0;
public int maxLength(List<String> arr) {
dfs(arr, 0, "");
return max;
}
public void dfs(List<String> arr, int index, String concatenatStr) {
if (isUnique(concatenatStr)) max = Math.max(max, concatenatStr.length());
if (index == arr.size() || !isUnique(concatenatStr)) return;
for (int i = index; i < arr.size(); i++) {
dfs(arr, i + 1, concatenatStr + arr.get(i));
}
}
public boolean isUnique(String s) {
int[] alpha = new int[26];
for (int i = 0; i < s.length(); i++) alpha[s.charAt(i) - 'a']++;
for (int i = 0; i < alpha.length; i++) if (alpha[i] > 1) return false;
return true;
}
}
