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
.
Example 1:
Input: arr = ["un","iq","ue"] Output: 4 Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique". Maximum length is 4.
Example 2:
Input: arr = ["cha","r","act","ers"] Output: 6 Explanation: Possible solutions are "chaers" and "acters".
Example 3:
Input: arr = ["abcdefghijklmnopqrstuvwxyz"] Output: 26
Constraints:
1 <= arr.length <= 16
1 <= arr[i].length <= 26
arr[i]
contains only lower case English letters.
Solution(javascript)
/*
* @lc app=leetcode id=1239 lang=javascript
*
* [1239] Maximum Length of a Concatenated String with Unique Characters
*/
// @lc code=start
/**
* @param {string[]} arr
* @return {number}
*/
const maxLength = function (arr) {
let max = 0
const isUnique = (s = '') => {
const map = {}
for (const c of s) {
map[c] = (map[c] || 0) + 1
if (map[c] >= 2) {
return false
}
}
return true
}
const aux = (index, current = '') => {
if (index > arr.length - 1) {
max = Math.max(current.length, max)
return
}
if (isUnique(current)) {
aux(index + 1, current)
if (isUnique(current + arr[index])) {
aux(index + 1, current + arr[index])
}
}
}
aux(0)
return max
}
// @lc code=end