##### Welcome to Subscribe On Youtube
• 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<>();

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))) {

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;
}
}

}

############

class Solution {
public int maxLength(List<String> arr) {
int ans = 0;
for (var s : arr) {
for (int i = 0; i < s.length(); ++i) {
int j = s.charAt(i) - 'a';
if (((mask >> j) & 1) == 1) {
break;
}
}
continue;
}
for (int i = 0; i < n; ++i) {
if ((m & mask) == 0) {
ans = Math.max(ans, Integer.bitCount(m | mask));
}
}
}
return ans;
}
}

• // OJ: https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/
// Time: O(2^N)
// Space: O(N)
class Solution {
public:
int maxLength(vector<string>& A) {
vector<int> v;
for (auto &s : A) {
int bs = 0, i = 0;
for (; i < s.size(); ++i) {
int j = s[i] - 'a';
if (bs >> j & 1) break;
bs |= 1 << j;
}
if (i == s.size()) v.push_back(bs);
}
int ans = 0;
for (int m = 1; m < 1 << v.size(); ++m) {
int bs = 0, i = 0;
for (; i < v.size(); ++i) {
if ((m >> i & 1) == 0) continue;
if (bs & v[i]) break;
bs |= v[i];
}
ans = max(ans, __builtin_popcount(bs));
}
return ans;
}
};

• class Solution:
def maxLength(self, arr: List[str]) -> int:
ans = 0
for s in arr:
for c in s:
i = ord(c) - ord('a')
if mask >> i & 1:
break
continue
if m & mask == 0:
ans = max(ans, (m | mask).bit_count())
return ans

############

# 1239. Maximum Length of a Concatenated String with Unique Characters
# https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/

class Solution:
def maxLength(self, A: List[str]):
dp = [set()]

for a in A:
if len(set(a)) < len(a): continue

a = set(a)
for b in dp[:]:
if a & b: continue
dp.append(a | b)

return max(len(a) for a in dp)

def maxLength(self, arr: List[str]):
n = len(arr)
res = 0

for i in range(1 << n):
tmp = ""
for j in range(n):
if i >> j & 1:
tmp += arr[j]

c = Counter(tmp)
if all(v == 1 for v in c.values()):
res = max(res, len(tmp))

return res

• func maxLength(arr []string) (ans int) {
for _, s := range arr {
for _, c := range s {
i := int(c - 'a')
break
}
}
continue
}
for _, m := range masks[:n] {
}
}
}
return
}

func max(a, b int) int {
if a > b {
return a
}
return b
}