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

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

Example 4:

``````Input: arr = ["aa","bb"]
Output: 0
Explanation: Both strings in arr do not have unique characters, thus there are no valid concatenations.
``````

Constraints:

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

``````class Solution {
public:
int maxLength(vector<string>& arr) {
return dfs(arr, "", 0);
}
int dfs(vector<string>& arr, string cur, int idx) {
unordered_set<char> st(cur.begin(), cur.end());
if (st.size() != cur.size()) return 0;
int res = cur.size();
for (int i = idx; i < arr.size(); ++i) {
res = max(res, dfs(arr, cur + arr[i], i + 1));
}
return res;
}
};
``````

``````class Solution {
public:
int maxLength(vector<string>& arr) {
vector<bitset<26>> all{bitset<26>()};
int res = 0;
for (string word : arr) {
bitset<26> cur;
for (char c : word) {
cur.set(c - 'a');
}
int n = cur.count();
if (n < word.size()) continue;
for (int i = (int)all.size() - 1; i >= 0; --i) {
bitset<26> t = all[i];
if ((t & cur).any()) continue;
all.push_back(t | cur);
res = max(res, (int)t.count() + n);
}
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1239

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

https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/discuss/414172/PythonC%2B%2BJava-Set-Solution

https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/discuss/414806/C%2B%2B-DFS-clean-and-concise-code.

LeetCode All in One 题目讲解汇总(持续更新中…)

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation