Algorithm
Problem Name: 1239. Maximum Length of a Concatenated String with Unique Characters
Problem Link: https://leetcode.com/problems/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.
Constraints:
1 <= arr.length <= 161 <= arr[i].length <= 26arr[i]contains only lowercase English letters.
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const maxLength = function(arr) {
let maxLen = 0;
arr = arr.filter(isUnique);
const mem = {};
maxLen = dfs(arr, "", 0, maxLen, mem);
return maxLen;
};
function dfs(arr, path, i, maxLen, mem) {
if (mem[path]) return mem[path];
let pathIsUnique = isUnique(path);
if (pathIsUnique) {
maxLen = Math.max(path.length, maxLen);
}
if (i === arr.length || !pathIsUnique) {
mem[path] = maxLen;
return maxLen;
}
for (let j = i; j < arr.length; j++) {
maxLen = dfs(arr, path + arr[j], j + 1, maxLen, mem);
}
mem[path] = maxLen;
return maxLen;
}
function isUnique(str) {
const map = {}
for (let i = 0; i < str.length; i++) {
if (map[str[i]]) return false;
map[str[i]] = 1;
}
return true;
}
Input
arr = ["un","iq","ue"]
Output
4
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def maxLength(self, arr: List[str]) -> int:
bfs = [""]
for b in filter(lambda x: len(x) == len(set(x)), arr):
bfs += [a + b for a in bfs if not set(a) & set(b)]
return max(map(len, bfs))
Input
arr = ["un","iq","ue"]
Output
4