Java | Easy to read code | Explained
The code is self explanatory and written modular in functions.\n\n# Intuition\n1. Sanitize input for duplicate words and bad words (word that contains duplicate
The code is self explanatory and written modular in functions.\n\n# Intuition\n1. Sanitize input for duplicate words and bad words (word that contains duplicate characters)\n2. Backtrack and find the largest possible solution\n\nWe can expand the backtrack search only if adding the word at the current index `i` doesn\'t cause a duplicate letter to appear. This is done efficiently by casting the strings `s1` and `s2` to sets and checking the intersection.\n\n# Code\n```\nimport java.util.*;\nimport java.util.stream.Collectors;\n\nclass Solution {\n    public int maxLength(List<String> arr) {\n        // Remove duplicate words and words with duplicate letters\n        List<String> sanitizedArr = Set.copyOf(arr)\n                        .stream()\n                        .filter(this::wordWithDuplicateLetter)\n                        .toList();\n\n        return maxLengthBacktrack(sanitizedArr, 0, "");\n    }\n\n    private boolean wordWithDuplicateLetter(String s) {\n        int[] letter = new int[26];\n        for (char chr : s.toCharArray()) {\n            letter[chr - \'a\']++;\n            if (letter[chr - \'a\'] > 1) {\n                return false;\n            }\n        }\n        return true;\n    }\n\n    private int maxLengthBacktrack(List<String> source, int index, String runningConcatenation) {\n        if (index == source.size()) {\n            return runningConcatenation.length();\n        }\n\n        int maxLength = 1;\n\n        // Option 1: don\'t concatenate\n        maxLength = Math.max(maxLength, maxLengthBacktrack(source, index + 1, runningConcatenation));\n\n        // Option 2: concatenate if you can\n        String currentWord = source.get(index);\n        if (!hasSharedCharacters(runningConcatenation.toString(), currentWord)) {\n            maxLength = Math.max(maxLength, maxLengthBacktrack(source, index + 1, runningConcatenation + currentWord));\n        }\n\n        return maxLength;\n    }\n\n    /**\n     * We want to make this operation O(|S1| + |S2|) and not O(|S1|*|S2|) therefore working with sets is easier as it is O(1) lookup\n     */\n    private boolean hasSharedCharacters(String s1, String s2) {\n        Set<String> setS1 = s1.chars().boxed().map(Character::toString).collect(Collectors.toSet());\n        Set<String> setS2 = s2.chars().boxed().map(Character::toString).collect(Collectors.toSet());\n        return setS1\n                .stream()\n                .anyMatch(setS2::contains);\n    }\n}\n```\n
['Java']