Maximum Length of a Concatenated String with Unique Characters — Solution

Problem

Given a list of strings, pick a subsequence of them (zero or more, in any order, each used at most once) and concatenate them together. Return the maximum length of such a concatenation where every character in the final string is unique.

• Input: arr = ["un", "iq", "ue"]
• Output: 4
• Explanation: "un" + "iq" = "uniq" has four distinct characters. Adding "ue" would repeat 'u', so the best we can do is length 4.

A string like "aab" can never appear in a valid result because it contains a duplicate 'a' internally — it would make any concatenation invalid regardless of what else is included.

Intuition

Each string contributes a set of characters, and two strings can coexist in the concatenation only when their character sets are completely disjoint. Representing each character set as a 26-bit integer (one bit per letter) turns the overlap check into a single bitwise AND — if the AND is zero, there is no shared character. Backtracking over all subsets then finds the longest valid combination without ever building or comparing strings character by character.

Solution — Bitmask Backtracking

Precompute a bitmask for each string (skipping those with internal duplicates), then explore all valid subsequences with backtracking, pruning any branch where the candidate string overlaps the characters already chosen.

1. For each string, walk its characters and set a bit for each letter in a 26-bit integer; if a bit is already set, the string has an internal duplicate and is discarded
2. Collect the (bitmask, length) pairs for all strings that passed the filter
3. Run backtracking from index 0 with an empty mask and length 0; update the global maximum at every node
4. At each step, loop over remaining strings (from the current index forward so each string is used at most once)
5. If a candidate's bitmask shares no bits with the current mask, include it and recurse with the combined mask and accumulated length
6. Return the maximum length recorded

1def maxLength(arr: list[str]) -> int:
2    def get_bitmask(word):
3        mask = 0
4        for ch in word:
5            bit = 1 << (ord(ch) - ord('a'))
6            if mask & bit:  # Duplicate character within this single word
7                return -1
8            mask |= bit
9        return mask
10
11    # Only keep words whose characters are all distinct
12    valid = [(get_bitmask(w), len(w)) for w in arr if get_bitmask(w) != -1]
13
14    max_length = 0
15
16    def backtrack(index, current_mask, current_length):
17        nonlocal max_length
18        max_length = max(max_length, current_length)
19        for i in range(index, len(valid)):
20            word_mask, word_len = valid[i]
21            if current_mask & word_mask == 0:  # No character overlap with chosen set
22                backtrack(i + 1, current_mask | word_mask, current_length + word_len)
23
24    backtrack(0, 0, 0)
25    return max_length

Time: O(2ⁿ) — each string is either included or excluded, giving at most 2ⁿ subsets to explore; bitmask operations are O(1)

Space: O(n) — the recursion stack depth is at most the number of valid strings

Complexity Summary

Common Mistakes

• Not filtering words with internal duplicate characters — a word like "aab" will always break uniqueness regardless of what it's combined with; checking only against the global mask won't catch this, because the word is only ever compared to previously chosen strings
• Starting the inner loop at index 0 instead of the current index — this allows the same word to be picked more than once, which is invalid since we need a subsequence where each element appears at most once
• Using current_mask & word_mask != 0 as the condition to include — the condition to add a word is that there is NO overlap, meaning the bitwise AND must equal zero, not be nonzero; this inversion produces the opposite behavior
• Calling get_bitmask twice per word — computing the mask once in the filter step and once in the valid list (as shown in the Python example above) doubles work; compute it once and store the result
• Omitting the recursion base case and only updating max at leaf nodes — since any prefix of a valid subsequence is also valid, the maximum can be achieved at an intermediate node, not just at depth n; update the max at every recursive call

Related Problems

• subsets — core subset enumeration pattern that this solution builds on
• combination-sum-ii — backtracking with an index-forward loop to avoid reusing elements
• palindrome-partitioning — backtracking that prunes invalid branches before recursing deeper
• maximum-product-of-word-lengths — uses the exact same bitmask trick to check whether two words share any characters in O(1)
• permutations — backtracking over selections with a visited marker, contrasted with the index-forward approach used here