1239-maximum-length-of-a-concatenated-string-with-unique-characters.py

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        charSet = set()

        def overlap(charSet, s):
            c = Counter(charSet) + Counter(s)
            return max(c.values()) > 1
            # prev = set()
            # for c in s:
            #     if c in charSet or c in prev:
            #         return True
            #     prev.add(c)
            # return False

        def backtrack(i):
            if i == len(arr):
                return len(charSet)
            res = 0
            if not overlap(charSet, arr[i]):
                for c in arr[i]:
                    charSet.add(c)
                res = backtrack(i + 1)
                for c in arr[i]:
                    charSet.remove(c)
            return max(res, backtrack(i + 1))  # dont concatenate arr[i]

        return backtrack(0)