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

}

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

# 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

1239 - Maximum Length of a Concatenated String with Unique Characters

All Problems

All Solutions