###### tags: `Leetcode` `medium` `string` `array` `python` `c++`

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

## [題目連結:] https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/description/

## 題目:
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.

## 解題想法:
* 此題為連接arr中的字串，連結條件為不可有重複字符
* return 最終max長度
* DFS遞迴判斷:
* def dfs(arr, curString, curPos):
* arr: 原數組
* curString: 當前串聯的字串
* curPos: arr中的位置
* dfs中每次判斷curString是否有重複字符
* **判斷方法**:
* len(set(curString))!=len(curString)
* 若不相等表示有重複字符: return 0
* for i in range(curPos, len(arr)):
* 往後遞迴

## Python:

class Solution(object):
    def maxLength(self, arr):
        """
        :type arr: List[str]
        :rtype: int
        """
        #連接字串，且不能有重複字符
        return self.dfs(arr,"",0)
    def dfs(self, arr, curString, curPos):
        curSet=set(curString)
        if len(curSet)!=len(curString):
            return 0
        res=len(curString)
        for i in range(curPos,len(arr)):
            res=max(res,self.dfs(arr, curString+arr[i], i+1))
        return res

## C++:

class Solution {
public:
    int maxLength(vector<string>& arr) {
        return dfs(arr, "", 0);
    }

    int dfs(vector<string>& arr, string curString, int curPos){
        unordered_set<char> curSet(curString.begin(), curString.end());
        if (curSet.size()!=curString.size()) //have duplicate char
            return 0;
        int res=curString.size();
        for (int i=curPos; i<arr.size(); i++){
            res=max(res, dfs(arr, curString+arr[i], i+1));
        }
        return res;
    }
};