1239. Maximum Length of a Concatenated String with Unique Characters

Problem

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 <= 16

• 1 <= arr[i].length <= 26

• arr[i] contains only lowercase English letters.

Solution

/**
 * @param {string[]} arr
 * @return {number}
 */
var maxLength = function(arr) {
    var maskArr = [];
    var newArr = [];
    var a = 'a'.charCodeAt(0);
    outter: for (var i = 0; i < arr.length; i++) {
        var num = 0;
        for (var j = 0; j < arr[i].length; j++) {
            var bit = (1 << (arr[i].charCodeAt(j) - a));
            if ((bit & num) !== 0) {
                continue outter;
            }
            num |= bit;
        }
        maskArr.push(num);
        newArr.push(arr[i]);
    }
    return dfs(newArr, maskArr, 0, 0);
};

var dfs = function(arr, maskArr, num, i) {
    if (i === arr.length) return 0;
    var len = dfs(arr, maskArr, num, i + 1);
    if ((maskArr[i] & num) === 0) {
        len = Math.max(len, arr[i].length + dfs(arr, maskArr, maskArr[i] | num, i + 1));
    }
    return len;
};

Explain:

Bit mask + DFS.

Complexity:

• Time complexity : O(2^n).
• Space complexity : O(n).