Java
import java.util.*;
/**
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: 4
Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
Maximum length is 4.
Example 2:
Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: 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.
*/
public class Maximum_Length_of_a_Concatenated_String_with_Unique_Characters {
public static void main(String[] args) {
Maximum_Length_of_a_Concatenated_String_with_Unique_Characters out = new Maximum_Length_of_a_Concatenated_String_with_Unique_Characters();
Solution s = out.new Solution();
ArrayList<String> input = new ArrayList<>();
// input.add("cha");
// input.add("r");
// input.add("act");
// input.add("ers");
input.add("un");
input.add("iq");
input.add("ue"); // output: 4
// input.add("yy");
// input.add("bkhwmpbiisbldzknpm");
System.out.println(s.maxLength(input));
}
class Solution {
int result = 0;
public int maxLength(List<String> array) {
Set<Integer> visitedIndex = new HashSet<>();
dfs("", 0, array, visitedIndex);
return result;
}
private void dfs(String s, int startIndex, List<String> array, Set<Integer> visitedIndex) {
System.out.println(s);
// System.out.println(startIndex + "\n");
if (isUniquestring(s)) {
result = Math.max(result, s.length());
} else {
return;
}
for (int i = startIndex; i < array.size(); i++) {
if (!visitedIndex.contains(i) && isUniqueChar(s, array.get(i))) {
visitedIndex.add(i);
dfs(s + array.get(i), i+1, array, visitedIndex);
visitedIndex.remove(i);
}
}
}
private boolean isUniqueChar(String s1, String s2) {
for (char each: s1.toCharArray()) {
if (s2.indexOf(each) >= 0) {
return false;
}
}
return true;
}
private boolean isUniquestring(String s) {
int[] charCount = new int[256];
for (char each: s.toCharArray()) {
charCount[each]++;
if (charCount[each] > 1) {
return false;
}
}
return true;
}
}
}