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

### Description

Given an array of strings `arr`. String `s` is a concatenation of a sub-sequence of `arr` which have **unique characters**.

Return *the maximum possible length* of `s`.

### Constraints

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

### Approach

### Links

* [Binarysearch](https://binarysearch.com/problems/Concatenated-String-of-Unique-Count)
* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/)
* ProgramCreek
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** arr = \["un", "iq", "ue"]

**Output:** 4

**Explanation:** All possible concatenations are "", "un", "iq", "ue", "uniq" and "ique".

Maximum length is 4.
{% endtab %}

{% tab title="Example 2" %}
**Input:** arr = \["cha", "r", "act", "ers"]

**Output:** 6

**Explanation:** Possible solutions are "chaers" and "acters".
{% endtab %}

{% tab title="Example 3" %}
**Input:** arr = \["abcdefghijklmnopqrstuvwxyz"]

**Output:** 26
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    private int maxLen = 0;
    
    public int maxLength(List<String> words) {
        if(words != null && !words.isEmpty()) {
            dfs(words, 0, "");
        }
        return maxLen;
    }
    
    private void dfs(List<String> words, int index, String word) {
        if(index > words.size()) {
            return;
        }
        
        if(isUniqueCharsInStr(word)) {
            maxLen = Math.max(maxLen, word.length());
        } else {
            return;
        }
        
        for(int i = index; i < words.size(); i++) {
            dfs(words, i+1, word + words.get(i));
        }
    }
    
    private boolean isUniqueCharsInStr(String s) {
        if(s.length() < 2) {
            return true;
        }
        Set<Character> set = new HashSet();
        for(char ch: s.toCharArray()) {
            if(set.contains(ch)) {
                return false;
            }
            set.add(ch);
        }
        return true;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*