> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Maximum Length of a Concatenated String with

> Tested Python solution for LeetCode 1239 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 1239, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [String](/catalog/topics/string), [Backtracking](/catalog/topics/backtracking), [Bit Manipulation](/catalog/topics/bit-manipulation). [View on LeetCode](https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/description/).

Generate this problem as a practice environment: tested reference solution, 16 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1239   # by problem number
lcpy gen -s maximum_length_of_a_concatenated_string_with_unique_characters   # by problem name
```

## 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.

### Examples

```
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.
```

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

```
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.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/maximum_length_of_a_concatenated_string_with_unique_characters/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/maximum_length_of_a_concatenated_string_with_unique_characters/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(2^n * n) worst case
    # Space: O(n)
    def max_len(self, arr: list[str]) -> int:
        masks: list[int] = []
        for s in arr:
            mask = 0
            for char in s:
                bit = 1 << (ord(char) - ord("a"))
                if mask & bit:
                    break
                mask |= bit
            else:
                masks.append(mask)
        best = 0

        def dfs(i: int, current: int) -> None:
            nonlocal best
            best = max(best, current.bit_count())
            for j in range(i, len(masks)):
                if not (current & masks[j]):
                    dfs(j + 1, current | masks[j])

        dfs(0, 0)
        return best
```

## Complexity

| Time | Space |
| - | - |
| O(2^n \* n) worst case | O(n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.