1239. Maximum Length of a Concatenated String With Unique Characters - Explanation

1. Backtracking (Hash Set)

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

        def overlap(charSet, s):
            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))

        return backtrack(0)

Time & Space Complexity

Time complexity: $O(m * 2 ^ n)$
Space complexity: $O(n)$ for recursion stack.

Where $n$ is the number of strings and $m$ is the maximum length of a string.

2. Backtracking (Boolean Array)

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

        def getIdx(c):
            return ord(c) - ord('a')

        def overlap(charSet, s):
            for i in range(len(s)):
                c = getIdx(s[i])
                if charSet[c]:
                    for j in range(i):
                        charSet[getIdx(s[j])] = False
                    return True
                charSet[c] = True
            return False

        def backtrack(i):
            if i == len(arr):
                return 0

            res = 0
            if not overlap(charSet, arr[i]):
                res = len(arr[i]) + backtrack(i + 1)
                for c in arr[i]:
                    charSet[getIdx(c)] = False
            return max(res, backtrack(i + 1))

        return backtrack(0)

Time & Space Complexity

Time complexity: $O(m * 2 ^ n)$
Space complexity: $O(n)$ for recursion stack.

Where $n$ is the number of strings and $m$ is the maximum length of a string.

3. Recursion (Bit Mask) - I

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        def getIdx(c):
            return ord(c) - ord('a')

        A = []
        for s in arr:
            cur = 0
            valid = True
            for c in s:
                if cur & (1 << getIdx(c)):
                    valid = False
                    break
                cur |= (1 << getIdx(c))

            if valid:
                A.append([cur, len(s)])

        def dfs(i, subSeq):
            if i == len(A):
                return 0

            res = dfs(i + 1, subSeq)

            curSeq, length = A[i][0], A[i][1]
            if (subSeq & curSeq) == 0:
                res = max(res, length + dfs(i + 1, subSeq | curSeq))
            return res

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(m * n + 2 ^ n)$
Space complexity: $O(n)$

Where $n$ is the number of strings and $m$ is the maximum length of a string.

4. Recursion (Bit Mask) - II

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        def getIdx(c):
            return ord(c) - ord('a')

        A = []
        for s in arr:
            cur = 0
            valid = True
            for c in s:
                if cur & (1 << getIdx(c)):
                    valid = False
                    break
                cur |= (1 << getIdx(c))

            if valid:
                A.append([cur, len(s)])

        def dfs(i, subSeq):
            res = 0
            for j in range(i, len(A)):
                curSeq, length = A[j][0], A[j][1]
                if (subSeq & curSeq) == 0:
                    res = max(res, length + dfs(j + 1, subSeq | curSeq))
            return res

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(n * (m + 2 ^ n))$
Space complexity: $O(n)$

Where $n$ is the number of strings and $m$ is the maximum length of a string.

5. Dynamic Programming

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        dp = {0}
        res = 0

        for s in arr:
            cur = 0
            valid = True

            for c in s:
                bit = 1 << (ord(c) - ord('a'))
                if cur & bit:
                    valid = False
                    break
                cur |= bit

            if not valid:
                continue

            next_dp = dp.copy()
            for seq in dp:
                if (seq & cur) or (seq | cur) in dp:
                    continue
                next_dp.add(seq | cur)
                res = max(res, bin(seq | cur).count('1'))
            dp = next_dp

        return res

Time & Space Complexity

Time complexity: $O(n * (m + 2 ^ n))$
Space complexity: $O(2 ^ n)$

Where $n$ is the number of strings and $m$ is the maximum length of a string.