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

}

All Problems

All Solutions