# Maximum Length of a Concatenated String with Unique Characters
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters)
Canonical: https://scaleengineer.com/dsa/problems/maximum-length-of-a-concatenated-string-with-unique-characters
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array, String
**Companies:** [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks)
---
## Problem
You are given an array of strings `arr`. A string `s` is formed by the **concatenation** of a **subsequence** of `arr` that has **unique characters**.

Return _the **maximum** possible length_ of `s`.

A **subsequence** is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

**Example 1:**

**Input:** arr = ["un","iq","ue"]
**Output:** 4
**Explanation:** All the valid concatenations are:
- ""
- "un"
- "iq"
- "ue"
- "uniq" ("un" + "iq")
- "ique" ("iq" + "ue")
Maximum length is 4.

**Example 2:**

**Input:** arr = ["cha","r","act","ers"]
**Output:** 6
**Explanation:** Possible longest valid concatenations are "chaers" ("cha" + "ers") and "acters" ("act" + "ers").

**Example 3:**

**Input:** arr = ["abcdefghijklmnopqrstuvwxyz"]
**Output:** 26
**Explanation:** The only string in arr has all 26 characters.

**Constraints:**

* `1 <= arr.length <= 16`
* `1 <= arr[i].length <= 26`
* `arr[i]` contains only lowercase English letters.

# Approaches
## Brute-Force by Generating All Subsequences
This approach explores every possible subsequence of the input array `arr`. For each subsequence, it concatenates the strings and then checks if the resulting string contains only unique characters. The length of each valid concatenated string is compared against a running maximum to find the final answer.
**Time:** O(2^N * S), where N is the number of strings and S is the total length of strings in a subsequence. In the worst case, this is O(2^N * N * L), where L is the max string length. For each of the 2^N subsequences, we concatenate and then validate the string, which takes time proportional to its length. · **Space:** O(N * L), where N is the number of strings and L is the maximum length of a string. This space is required to store the longest possible concatenated string.
**Pros:** Conceptually simple and straightforward to implement.
**Cons:** Highly inefficient due to repeated string concatenations and uniqueness checks.; The time complexity makes it infeasible for larger constraints, though it might pass for `N <= 16` due to the small problem size.
### Explanation
The core idea is to treat the problem as finding the best subset of strings. Since there are `n` strings in the input array, there are `2^n` possible subsets (or subsequences). We can systematically generate each one. A common way to do this is to loop from `0` to `2^n - 1`. Each number in this range can be seen as a bitmask of length `n`. If the `j`-th bit is set in the number `i`, we include the `j`-th string from `arr` in our current subsequence. After forming the subsequence, we join its strings and perform a check for character uniqueness. This check involves iterating through the concatenated string and using an auxiliary data structure like a boolean array of size 26 to track seen characters. If the string is valid, we update our maximum length.

```java
import java.util.List;

class Solution {
    public int maxLength(List<String> arr) {
        int maxLength = 0;
        int n = arr.size();
        // Iterate through all 2^n possible subsequences
        for (int i = 0; i < (1 << n); i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                // Check if the j-th bit is set in i
                if ((i & (1 << j)) != 0) {
                    sb.append(arr.get(j));
                }
            }
            String concatenated = sb.toString();
            if (hasUniqueCharacters(concatenated)) {
                maxLength = Math.max(maxLength, concatenated.length());
            }
        }
        return maxLength;
    }

    private boolean hasUniqueCharacters(String s) {
        if (s.length() > 26) {
            return false;
        }
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            if (freq[c - 'a'] > 0) {
                return false;
            }
            freq[c - 'a']++;
        }
        return true;
    }
}
```
### Algorithm
- Initialize a variable `maxLength` to 0.
- Generate all `2^n` possible subsequences of the input array `arr`, where `n` is the number of strings in `arr`.
- This can be done by iterating from `0` to `2^n - 1` and using the binary representation of the loop counter to select which strings to include in the subsequence.
- For each subsequence:
  - Concatenate all the strings in the subsequence to form a single string `s`.
  - Use a helper function to check if `s` contains only unique characters. This is typically done using a frequency array or a hash set.
  - If `s` has unique characters, update `maxLength` with the maximum of its current value and the length of `s`.
- After iterating through all subsequences, return `maxLength`.

## Iterative Approach with Bitmasks
This approach builds up the set of all possible valid concatenations iteratively. It uses bitmasks to efficiently represent the set of characters in a string, avoiding costly string operations. A list stores the bitmasks of all valid concatenations found so far. For each string in the input array, it tries to combine it with existing valid concatenations, creating new ones if there are no character conflicts.
**Time:** O(N * L + 2^N). We spend O(N * L) to preprocess all strings into masks. The main logic involves nested loops where the total number of inner iterations across all outer loops is O(2^N). · **Space:** O(2^N), where N is the number of strings. The `dp` list can store up to 2^N masks in the worst case.
**Pros:** Much more efficient than the naive brute-force by using fast bitwise operations instead of string manipulation.; The logic is iterative, which can be easier to reason about than recursion for some.
**Cons:** The space complexity is O(2^N), which can be memory-intensive. For N=16, this means storing up to 65,536 integers.
### Explanation
Instead of generating subsequences and then checking them, we can build the valid results incrementally. We maintain a list of bitmasks, where each mask represents the character set of a valid concatenated string. We start with a list containing just `0` (for an empty string). Then, for each string in the input array, we try to extend every valid result we've found so far. 

First, we convert the current string `s` into a bitmask, but only if `s` itself contains unique characters. If it does, we iterate through our current list of valid masks. For each existing mask, we check if combining it with the new string's mask would result in a conflict (i.e., a shared character). A bitwise AND operation (`&`) makes this check extremely fast. If there's no conflict, we create a new mask by combining them with a bitwise OR (`|`) and add it to our set of results. We keep track of the maximum length (which is the number of set bits in a mask) as we generate new masks.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int maxLength(List<String> arr) {
        List<Integer> dp = new ArrayList<>();
        dp.add(0); // Start with an empty string mask
        int maxLength = 0;

        for (String s : arr) {
            int sMask = 0;
            int dupCheckMask = 0;
            for (char c : s.toCharArray()) {
                // Check for duplicates within the string s itself
                if ((dupCheckMask & (1 << (c - 'a'))) != 0) {
                    sMask = 0; // Mark as invalid
                    break;
                }
                dupCheckMask |= (1 << (c - 'a'));
            }
            sMask = dupCheckMask;

            if (sMask == 0) {
                continue; // Skip strings with duplicate characters
            }

            int currentSize = dp.size();
            for (int i = 0; i < currentSize; i++) {
                int existingMask = dp.get(i);
                // If no character overlap
                if ((existingMask & sMask) == 0) {
                    int newMask = existingMask | sMask;
                    dp.add(newMask);
                    maxLength = Math.max(maxLength, Integer.bitCount(newMask));
                }
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize a list, `dp`, containing one element: `0`. This represents the bitmask for an empty string.
- Initialize `maxLength = 0`.
- Iterate through each string `s` in the input array `arr`.
  - First, calculate the bitmask for `s`, let's call it `sMask`. During this calculation, also check if `s` itself has duplicate characters. If it does, it cannot be part of any valid concatenation, so we skip it.
  - Create a temporary list to store new masks generated in this iteration.
  - Iterate through each `existingMask` currently in the `dp` list.
    - Check for character conflicts using a bitwise AND: `(sMask & existingMask) == 0`.
    - If there are no conflicts, a new valid concatenation is possible. Its mask is `newMask = sMask | existingMask`.
    - Add `newMask` to the temporary list.
    - Update `maxLength = max(maxLength, Integer.bitCount(newMask))`.
  - After checking against all existing masks, add all masks from the temporary list to the `dp` list.
- After iterating through all strings, `maxLength` will hold the answer.

## Backtracking with Bitmasks
This is a recursive depth-first search (DFS) approach, often called backtracking. It efficiently explores the decision of either including or excluding each string from the final concatenation. The key to its efficiency is using bitmasks to represent character sets, which avoids costly string operations. We also pre-process the input array to filter out strings that contain duplicate characters themselves, as they can never be part of a valid solution.
**Time:** O(N * L + 2^N). O(N * L) for the initial filtering and mask creation. The backtracking function explores at most 2^N states, and each step involves constant-time bitwise operations. · **Space:** O(N), where N is the number of strings. This space is dominated by the depth of the recursion call stack.
**Pros:** Optimal time complexity for this problem's constraints.; Very space-efficient, using only O(N) space for the recursion stack.; A standard and powerful technique for subset/subsequence problems.
**Cons:** Recursion can lead to a stack overflow for very large N, but given N <= 16, this is not a concern here.
### Explanation
This approach models the problem as a state-space search. Each state is defined by the current string we are considering and the set of characters used so far. We use a recursive function to explore this space. The function decides for each string `s` whether to add it to our current sequence or skip it.

To make this efficient, we first filter the input `arr`, keeping only strings with unique characters and converting them to integer bitmasks. Then, our recursive function `backtrack(index, currentMask)` explores the possibilities. At each step, we have a choice: for each subsequent string (from `index` onwards), we can try to append it. We can only append it if its characters don't overlap with the `currentMask`. We check this with a fast `(currentMask & nextMask) == 0` operation. If they don't overlap, we recurse deeper with an updated mask `currentMask | nextMask`. We update the maximum length found at every valid state in our search, not just at the leaves of the recursion tree.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    private int maxLength = 0;

    public int maxLength(List<String> arr) {
        List<Integer> uniqueMasks = new ArrayList<>();
        for (String s : arr) {
            int mask = 0;
            boolean hasDuplicates = false;
            for (char c : s.toCharArray()) {
                if ((mask & (1 << (c - 'a'))) != 0) {
                    hasDuplicates = true;
                    break;
                }
                mask |= (1 << (c - 'a'));
            }
            if (!hasDuplicates) {
                uniqueMasks.add(mask);
            }
        }
        backtrack(0, 0, uniqueMasks);
        return maxLength;
    }

    private void backtrack(int index, int currentMask, List<Integer> uniqueMasks) {
        maxLength = Math.max(maxLength, Integer.bitCount(currentMask));

        for (int i = index; i < uniqueMasks.size(); i++) {
            int nextMask = uniqueMasks.get(i);
            // Check for conflict
            if ((currentMask & nextMask) == 0) {
                // Recurse with the new mask
                backtrack(i + 1, currentMask | nextMask, uniqueMasks);
            }
        }
    }
}
```
### Algorithm
- **Preprocessing:**
  - Create a list to store the integer bitmasks of strings from `arr` that contain only unique characters. 
  - Iterate through `arr`. For each string, calculate its bitmask. If the string has duplicate characters, discard it. Otherwise, add its mask to the list.
- **Recursion:**
  - Define a recursive function, `backtrack(index, currentMask)`.
    - `index`: The starting index in the list of masks to consider for concatenation.
    - `currentMask`: The bitmask of the string formed so far.
  - **Inside `backtrack`:**
    - First, update a global `maxLength` with the number of set bits in `currentMask` (`Integer.bitCount(currentMask)`).
    - Iterate from `i = index` to the end of the masks list.
      - Let `nextMask` be the mask at index `i`.
      - Check for character conflicts: `(currentMask & nextMask) == 0`.
      - If there are no conflicts, it's a valid extension. Make a recursive call to explore this path: `backtrack(i + 1, currentMask | nextMask)`.
- **Initial Call:** Start the process by calling `backtrack(0, 0)`.
- Return the final `maxLength`.

# Solutions
### Java

```java
class Solution {
public
  int maxLength(List<String> arr) {
    int ans = 0;
    List<Integer> masks = new ArrayList<>();
    masks.add(0);
    for (var s : arr) {
      int mask = 0;
      for (int i = 0; i < s.length(); ++i) {
        int j = s.charAt(i) - 'a';
        if (((mask >> j) & 1) == 1) {
          mask = 0;
          break;
        }
        mask |= 1 << j;
      }
      if (mask == 0) {
        continue;
      }
      int n = masks.size();
      for (int i = 0; i < n; ++i) {
        int m = masks.get(i);
        if ((m & mask) == 0) {
          masks.add(m | mask);
          ans = Math.max(ans, Integer.bitCount(m | mask));
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxLength(vector<string> &arr) {
    int ans = 0;
    vector<int> masks = {0};
    for (auto &s : arr) {
      int mask = 0;
      for (auto &c : s) {
        int i = c - 'a';
        if (mask >> i & 1) {
          mask = 0;
          break;
        }
        mask |= 1 << i;
      }
      if (mask == 0) {
        continue;
      }
      int n = masks.size();
      for (int i = 0; i < n; ++i) {
        int m = masks[i];
        if ((m & mask) == 0) {
          masks.push_back(m | mask);
          ans = max(ans, __builtin_popcount(m | mask));
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxLength(self, arr: List[str]) -> int: ans = 0 masks = [0] for s in arr: mask = 0 for c in s: i = ord(c) - ord('a') if mask >> i & 1: mask = 0 break mask |= 1 << i if mask == 0: continue for m in masks: if m & mask == 0: masks . append(m | mask) ans = max(ans, (m | mask). bit_count()) return ans

```