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

1. Backtracking (Hash Set)

Intuition

We want to find the longest concatenation of strings where all characters are unique. Since we need to try different combinations of strings, backtracking is a natural fit. For each string, we have two choices: include it (if it doesn't conflict with already chosen characters) or skip it. A hash set helps us efficiently check for character conflicts between the current selection and the next candidate string.

Algorithm

Use a hash set charSet to track characters in the current concatenation.
Create a helper function overlap that checks if a string has duplicate characters within itself or conflicts with charSet.
Use backtracking starting from index 0. At each index i:
- If the string at i doesn't overlap, add its characters to charSet, recurse to i + 1, then remove the characters (backtrack).
- Always try skipping the current string by recursing to i + 1 without adding it.
Return the maximum length found when reaching the end of the array.

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)

Intuition

Since we only deal with lowercase letters, we can replace the hash set with a fixed-size boolean array of length 26. This provides faster lookups and updates while reducing memory overhead. The overlap check simultaneously marks characters as used, and if a conflict is found, we undo the partial marking before returning.

Algorithm

Use a boolean array charSet of size 26 to track which characters are currently in use.
In the overlap function, iterate through the string. For each character, if it's already marked, undo all previous markings from this string and return true. Otherwise, mark it as used.
Use backtracking starting from index 0. At each index i:
- If the string at i doesn't overlap, recurse and add its length to the result, then clear its characters from charSet.
- Compare with the result of skipping the current string.
Return the maximum total length.

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

Intuition

We can represent the character set of each string as a bitmask, where bit i is set if the character 'a' + i is present. Two strings conflict if their bitmasks share any set bits (i.e., their AND is non-zero). This allows O(1) conflict detection. We preprocess strings to filter out those with internal duplicates and convert valid ones to bitmasks.

Algorithm

Preprocess: for each string, build its bitmask. If any character appears twice (detected by checking if the bit is already set), skip the string. Store valid strings as pairs of (bitmask, length).
Use recursion with parameters i (current index) and subSeq (bitmask of characters used so far).
At each index, first try skipping the string. Then, if the current string's mask doesn't conflict with subSeq (AND equals zero), try including it by OR-ing the masks and adding its length.
Return the maximum length found.

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

Intuition

This is a variation of the bitmask recursion that uses a different traversal pattern. Instead of explicitly choosing to skip or include each string, we iterate through all remaining strings and only recurse when we find a compatible one. This approach naturally prunes branches where strings conflict, though the overall complexity remains similar.

Algorithm

Preprocess strings into bitmask and length pairs, filtering out strings with duplicate characters.
Use recursion with parameters i (starting index) and subSeq (current character bitmask).
In each call, iterate from index i to the end. For each string whose mask doesn't conflict with subSeq, recurse with the combined mask and track the maximum length achieved.
Return the maximum result found across all branches.

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

Intuition

Instead of recursion, we can build solutions iteratively. We maintain a set of all unique bitmasks we can achieve so far. For each new valid string, we try combining it with every existing bitmask in our set. If they don't conflict, we add the combined mask to our collection. The answer is the maximum number of set bits among all masks.

Algorithm

Initialize a set dp containing just 0 (representing the empty selection).
For each string, compute its bitmask. Skip strings with duplicate characters.
For each existing mask seq in dp, check if it conflicts with the current string's mask. If not, add seq | cur to a new set and update the maximum bit count.
After processing all strings, return the maximum bit count found (which equals the maximum length since each bit represents one unique character).

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.

Common Pitfalls

Not Filtering Strings with Internal Duplicates

A string like "aa" or "abca" contains duplicate characters within itself. Such strings can never be part of a valid concatenation since the result must have all unique characters. Failing to preprocess and filter out these invalid strings leads to wasted computation and potentially incorrect results if the overlap check only compares against previously selected characters but not within the string itself.

Incorrect Bitmask Conflict Detection

When using bitmasks, two strings conflict if their AND is non-zero (they share at least one character). A common mistake is using OR or XOR for conflict detection, or checking equality instead of bitwise AND. The correct check is (mask1 & mask2) == 0 to confirm no overlapping characters before combining with mask1 | mask2.

Forgetting to Backtrack

In the backtracking solution, after exploring the branch where a string is included, you must remove its characters from the set before exploring the skip branch. Forgetting to undo the state change causes characters from the "include" path to pollute the "skip" path, leading to false conflicts and suboptimal results. The bitmask approach avoids this issue since the mask is passed by value in recursion.