Java | 4 solutions
4.DFS + bit manipulation\n\n\t//4.DFS + bit manipulation\n    //Runtime: 1 ms, faster than 100.00% of Java online submissions for Maximum Length of a Concatenat
# 4.DFS + bit manipulation\n```\n\t//4.DFS + bit manipulation\n    //Runtime: 1 ms, faster than 100.00% of Java online submissions for Maximum Length of a Concatenated String with Unique Characters.\n    //Memory Usage: 39.6 MB, less than 99.30% of Java online submissions for Maximum Length of a Concatenated String with Unique Characters.\n    //Time: O(2^N); Space: O(N)\n    public int maxLength(List<String> arr) {\n        List<Integer> arr2 = new ArrayList<>();\n        for(String word: arr) {\n            int bitSet = str2BitInt4(word);\n            if (bitSet > 0) arr2.add(str2BitInt4(word));\n        }\n        int[] data = new int[arr2.size()];\n        for (int i = 0; i < data.length; i++)\n            data[i] = arr2.get(i);\n\n        return helper_dfs(data, 0, 0);\n    }\n    private int helper_dfs(int[] data, int begin, int bitSet) {\n        int maxLen = Integer.bitCount(bitSet);\n        for (int i = begin; i < data.length; i++) {\n            if ((data[i] | bitSet) == (data[i] ^ bitSet))\n                maxLen = Math.max(maxLen, helper_dfs(data, i + 1, bitSet | data[i]));\n        }\n        return maxLen;\n    }\n\n    private int str2BitInt4(String word){\n        int x = 0;\n        for(char c : word.toCharArray()) {\n            if ((x >> (c - \'a\') & 1) == 1) return -1;\n            x |= 1 << c - \'a\';\n        }\n        return x;\n    }\n```\n# 3.Bit manipulation\n```\n    //3.Bit manipulation\n    //Runtime: 9 ms, faster than 91.52% of Java online submissions for Maximum Length of a Concatenated String with Unique Characters.\n    //Memory Usage: 42.3 MB, less than 84.45% of Java online submissions for Maximum Length of a Concatenated String with Unique Characters.\n    public int maxLength_3(List<String> arr) {\n        int mask = (1<<26) - 1;\n        List<Integer> result = new ArrayList<>();\n        result.add(0);\n        int maxLen = 0;\n        for (String word : arr) {\n            int x = str2BitInt3(word);\n            if (x < 1) continue;\n\n            int resultSize = result.size();\n            //Time: O((2 ^ N) * K)\n            for (int i = 0; i < resultSize; i++) {\n                int currX = result.get(i) | x;\n                if (currX == (result.get(i) ^ x)) {\n                    //int currLen = Integer.bitCount(currX);\n                    int currLen = (result.get(i) >> 26) + word.length();\n                    maxLen = Math.max(maxLen, currLen);\n                    currX = currX & mask | (currLen << 26);\n                    result.add(currX);\n                }\n            }\n        }\n        return maxLen;\n    }\n\n    //Time:O(K)\n    private int str2BitInt3(String word){\n        int x = 0;\n        for(char c : word.toCharArray()) {\n            if ((x >> (c - \'a\') & 1) == 1) return -1;\n            x |= 1 << c - \'a\';\n        }\n        return x;\n    }\n```\n# 2.Iteration\n```\n    //2.Iteration\n    //Runtime: 30 ms, faster than 66.54% of Java online submissions for Maximum Length of a Concatenated String with Unique Characters.\n    //Memory Usage: 46.4 MB, less than 67.87% of Java online submissions for Maximum Length of a Concatenated String with Unique Characters.\n    public int maxLength_2(List<String> arr) {\n        int maxLen = 0;\n        List<String> result = new ArrayList<>();\n        result.add("");\n        for (String word : arr) {\n            int resultSize = result.size();\n            for (int i = 0; i < resultSize; i++) {\n                //Time: O(K); Space: O(K)\n                String word2 = result.get(i) + word;\n                //Time: O(K)\n                if (isSelfUnique2(word2)){\n                    result.add(word2);\n                    maxLen = Math.max(maxLen, word2.length());\n                }\n            }\n        }\n        return maxLen;\n    }\n    //Time: O(K)\n    private boolean isSelfUnique2(String str){\n        Set<Character> strSet = new HashSet<>();\n        for(char c : str.toCharArray())\n            if (!strSet.add(c)) return false;\n        return true;\n    }\n```\n# 1.array + backtracking word\n```\n    //1.array + backtracking word\n    //Runtime: 179 ms, faster than 16.50% of Java online submissions for Maximum Length of a Concatenated String with Unique Characters.\n    //Memory Usage: 117.1 MB, less than 11.78% of Java online submissions for Maximum Length of a Concatenated String with Unique\n    public int maxLength_1(List<String> arr) {\n        List<String> arr2 = new ArrayList<>();\n        for (String str : arr)\n            if (isSelfUnique(str)) arr2.add(str);\n        return helper_backtracking1(arr2, 0, new int[26]);\n    }\n\n    private int helper_backtracking1(List<String> arr, int begin, int[] counter) {\n        int count = 0;\n\n        if (begin >= arr.size()) {\n            for (int n : counter) if (n != 0) count++;\n            return count;\n        }\n\n\n        Set<Integer> toBeRemoveSet = new HashSet<>();\n        if (isContainAny(counter, arr.get(begin))){\n            count = Math.max(count, helper_backtracking1(arr, begin + 1, counter));\n\n            //remove prev\n            for(char c : arr.get(begin).toCharArray()) {\n                if (counter[c - \'a\'] != 0) {\n                    int idx = counter[c - \'a\'] - 1;\n                    if (toBeRemoveSet.add(idx))\n                        removeFromSet(counter, arr.get(idx));\n                }\n            }\n        }\n\n        addToSet(counter, arr.get(begin), begin);\n        count = Math.max(count, helper_backtracking1(arr, begin + 1, counter));\n        removeFromSet(counter, arr.get(begin));\n\n        for (int toBeRemoveIdx: toBeRemoveSet)\n            addToSet(counter,arr.get(toBeRemoveIdx), toBeRemoveIdx);\n\n        return count;\n    }\n\n    private boolean isSelfUnique(String str){\n        Set<Character> strSet = new HashSet<>();\n        for(char c : str.toCharArray())\n            if (!strSet.add(c)) return false;\n        return true;\n    }\n\n    private boolean isContainAny(int[] data, String str){\n        for(char c : str.toCharArray())\n            if (data[c - \'a\'] != 0) return true;\n        return false;\n    }\n\n    private void addToSet(int[] data, String str, int i){\n        i++;\n        for(char c : str.toCharArray()) data[c - \'a\'] = i;\n    }\n\n    private void removeFromSet(int[] data, String str){\n        for(char c : str.toCharArray()) data[c - \'a\'] = 0;\n    }\n```
['Backtracking', 'Bit Manipulation', 'Depth-First Search', 'Java']