> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/bit-masking/1239.-maximum-length-of-a-concatenated-string-with-unique-characters.md).

# 1239. Maximum Length of a Concatenated String with Unique Characters

## Problem Statement

<br>

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.

&#x20;

**Example 1:**

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

**Example 2:**

<pre><code><strong>Input: arr = ["cha","r","act","ers"]
</strong><strong>Output: 6
</strong><strong>Explanation: Possible longest valid concatenations are "chaers" ("cha" + "ers") and "acters" ("act" + "ers").
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
</strong><strong>Output: 26
</strong><strong>Explanation: The only string in arr has all 26 characters.
</strong></code></pre>

&#x20;

**Constraints:**

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

## Intuition

```
Approach:

For 26 characters maintain a mask ,
Also keep lenght in the remaining bits 

Now, in the early stages we eliminate aabc like strings to eliminate faltu branches
```

### Links

<https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/>

### Video Links

<https://www.youtube.com/watch?v=FoqN_xSZ-Is&ab_channel=AryanMittal>

### Approach 1:

```
Bit Manipulation
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    void wordBit(unordered_set<int> &st, string &str){
        int bit=0;
        for(auto &it: str){
            int temp = 1 << (it-'a');
            if(temp & bit)  return ;
            bit += temp; 
        }
        int len = str.size() << 26;
        st.insert(bit + len);
    }

    int find_ans(vector<int> &nums, int index, int mask){
        int oldMask = mask & ((1<<26) - 1);
        int oldLen = mask >> 26;
        int ans = oldLen;

        if(index >= nums.size())
            return ans;


        int newMask = nums[index] & ((1<<26) - 1);
        if(!(oldMask & newMask)){
            int newLen = nums[index] >> 26;
            int newMask = oldMask + newMask + ((newLen + oldLen) << 26);
            ans = max(ans, find_ans(nums, index+1, newMask));
        }

        ans = max(ans, find_ans(nums, index+1, mask));
        return ans;
    }

    int maxLength(vector<string>& arr) {
        unordered_set<int> st;
        for(auto &it: arr)
            wordBit(st, it);

        vector<int> nums(st.begin(), st.end());
        return find_ans(nums, 0, 0);
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###