Simple Backtrack Beats 96% time, 78% space Python
Intuition\n Describe your first thoughts on how to solve this problem. \nSmall parameter length constraints suggest backtracking is in play.\n\n# Approach\n Des
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSmall parameter length constraints suggest backtracking is in play.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFirst, remove invalid entries in arr.  Next, evaluate each item in arr, and try each case: including and excluding curr sub_arr item (if item can be added and keep string valid)\n\n# Complexity\n- Time complexity: O(2**N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n-> N is length of array\n\n# Code\n```\nclass Solution:\n    def maxLength(self, arr: List[str]) -> int:\n        # sanitize: remove invalid subarrays from arr\n        arr = [sub_arr for sub_arr in arr if len(sub_arr) == len(set(sub_arr))]\n\n        self.res = 0\n        n = len(arr)\n        def backtrack(i: int, s: str):\n            if i >= n:\n                self.res = max(len(s), self.res)\n                return\n            \n            curr = arr[i]\n            valid = True\n            for char in set(curr):\n                if char in s:\n                    valid = False\n                    break\n            # case: exclude curr\n            backtrack(i+1, s)\n            # case: include curr, if possible\n            if valid:\n                backtrack(i+1, s + curr)\n\n        backtrack(0, "")\n        return self.res\n```
['Hash Table', 'Backtracking', 'Recursion', 'Python', 'Python3']