Maximum Length of a Concatenated String with Unique Characters

How it works

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.

Steps

1. Initialize a set dp containing just 0 (representing the empty selection).
2. For each string, compute its bitmask. Skip strings with duplicate characters.
3. 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.
4. After processing all strings, return the maximum bit count found (which equals the maximum length since each bit represents one unique character).

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.

Things to watch for

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.

from typing import List

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

class Solution {
public:
    int maxLength(vector<string>& arr) {
        unordered_set<int> dp;
        dp.insert(0);
        int res = 0;

        for (const string& s : arr) {
            int cur = 0;
            bool valid = true;

            for (char c : s) {
                int bit = 1 << (c - 'a');
                if (cur & bit) {
                    valid = false;
                    break;
                }
                cur |= bit;
            }

            if (!valid) {
                continue;
            }

            unordered_set<int> next_dp(dp);
            for (int seq : dp) {
                if ((seq & cur) || next_dp.count(seq | cur)) {
                    continue;
                }
                next_dp.insert(seq | cur);
                res = max(res, __builtin_popcount(seq | cur));
            }
            dp = next_dp;
        }

        return res;
    }
};