Java simple backtracking using sets, with explanation
In a real interview, I would have asked for clarification: "Can a certain string contain duplicate characters by itself?". They should have made it clear in the
In a real interview, I would have asked for clarification: "Can a certain string contain duplicate characters by itself?". They should have made it clear in the sample test cases or in the description. I\'d like to point out that in this problem, duplicate characters are allowed in input strings. For example, ["aa","bc","ac"] is a valid input.\n\nThe time complexity will be **O(2^n)** because I choose or not choose each string for every previous choice.\nThe space complexity will be **O(n)** because I will keep a set of all string characters, and the longest set at any point will contain atmost 26 characters (constant).\n\n```\nclass Solution {\n        List<Set<Character>> sets = new ArrayList<>();\n        int maxLength = 0;\n    public int maxLength(List<String> arr) {\n        // to make sure that terms with existing letters are not considered\n        // keep track of seen letters\n        // because all need to be unique, use a set\n        // if two sets are disjoint, then combine them, or not\n        for(String a : arr){\n            Set<Character> curr = new HashSet<>();\n            for(char c : a.toCharArray()){\n                curr.add(c);\n            }\n            sets.add(curr);\n        }\n        tryConcatenations(arr, 0, new HashSet<>());\n        \n        return maxLength;\n    }\n    \n    private void tryConcatenations(List<String> arr, int index, Set<Character> currentSet){\n        // update maxLength to current if greater\n\t\t// if any string is added, this recursive function will always be called with i+1 as index\n\t\t// so, maxlength will always be updated whenever a new set of characters is added to the result\n        maxLength = Math.max(maxLength, currentSet.size());\n        \n        for(int i = index; i < arr.size(); i++){\n            // check if the string itself contains repeated characters\n            if(arr.get(i).length() != sets.get(i).size())\n                continue;\n            // take this string and split its characters (done in global "sets")\n            // if there is any character in current sequence then don\'t add\n            boolean repeats = false;\n            for(char c : sets.get(i)){\n                if(currentSet.contains(c)){\n                    repeats = true;\n                    break;\n                }\n            }\n            // if unique characters then proceed\n            if(!repeats){\n                Set<Character> nextSet = new HashSet<>(currentSet);\n                nextSet.addAll(sets.get(i));\n\t\t\t\t// calling the function with the current string added\n                tryConcatenations(arr, i+1, nextSet);\n            }\n        }\n        // the case where the current string is not added will be considered in all further iterations of this loop\n    }\n}\n```\n**Please upvote if you found the solution helpful.**
['Backtracking', 'Depth-First Search', 'Recursion', 'Java']