1239. Maximum Length of a Concatenated String with Unique Characters

Maximum Length of a Concatenated String with Unique Characters

Problem Description

You are given an array of strings arr. A string s is formed by concatenating a subsequence with 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.

Approach) Brute Force

Idea is to create all possible combinations and calculate the max string which is having all unique characters in it without messing up the order

/**
 * @param {string[]} arr
 * @return {number}
 */
var maxLength = function(arr) {
    const set = new Set(['']);
    let max = 0;
    let str;
    
    for(let i = 0; i < arr.length; i++) {
        const values = [...set.values()];
        
        for(let j = 0; j < values.length; j++) {     
            str = `${values[j]}${arr[i]}`;
            set.add(str);
            let newStr = [...new Set(str).values()].join('');
            
            if (str === newStr) {
                max = Math.max(str.length, max);    
            }            
        }
    }
    
    return max;
};

Approach) Hash set

/**
 * @param {string[]} arr
 * @return {number}
 */
var maxLength = function (arr) {
  const ans = { val: 0 };
  helper(arr, 0, ans, new Set([]));

  return ans.val;
};

function helper(arr, idx, ans, set) {
  if (idx === arr.length) {
    ans.val = Math.max(ans.val, set.size);
    return;
  }

  helper(arr, idx + 1, ans, set);

  if (isPossibleToPick(arr[idx], set)) {
    const newSet = new Set(set);
    for (const char of arr[idx]) newSet.add(char);
    helper(arr, idx + 1, ans, newSet);
  }
}

function isPossibleToPick(word, set) {
  const containsDuplicate = new Set(word.split('')).size !== word.length;
  if (containsDuplicate) return false;

  for (const char of word) {
    if (set.has(char)) return false;
  }
  return true;
}

Approach) Depth First Search (DFS) Recursion

var maxLength = function (arr) {
    function hasUniqueChars(word) {
        const map = new Map();
        for (let i = 0; i < word.length; i++) {
            const c = word[i];
            if (map.has(c)) return false;
            map.set(c, true);
        }
        return true;
    }
    let res = 0;
    function dfs(idx, str) {
        if (idx === arr.length) return;
        const newStr = str + arr[idx];

        if (hasUniqueChars(newStr)) {
            res = Math.max(res, newStr.length);
            dfs(idx + 1, newStr);
        }
        dfs(idx + 1, str);
    }
    dfs(0, '');
    return res;
};

Approach) Dynamic Programming

const maxLength = arr => {
  let res = 0;

  const dp = (idx, cur) => {
    res = Math.max(res, cur.length);
    for (let i = idx; i < arr.length; i++) {
      ((cur+arr[i]).length === new Set([...cur,...arr[i]]).size) && 
        dp(i + 1, cur + arr[i]);
    }
  }

  dp(0, '');
  return res;
};

An alternate method to check for duplicates. Including because it's a more versatile approach and can be used
to determine which chars are duplicates if modified, etc. Not necessary for this problem though.

const maxLength = arr => {
  let res = 0;

  const dp = (idx, cur) => {
    res = Math.max(res, cur.length);
    
    for (let i = idx; i < arr.length; i++) {
      
      const unique = !!([...cur, ...arr[i]].reduce((set, char) => {
        if (!set || set.has(char)) return false;
        return set.add(char)
      }, new Set())); 
      
      if (unique) dp(i + 1, cur + arr[i]);
    }
  }

  dp(0, '');
  return res;
};

Approach) Bit Map

/**
 * @param {string[]} arr
 * @return {number}
 */

var charToNum = {
        a: 1, b: 2, c: 3, d: 4, e: 5, f: 6, g: 7, h: 8, i: 9, j: 10, k: 11, l: 12, m: 13, n: 14,o: 15, p: 16, q: 17, r: 18, s: 19, t: 20, u: 21, v: 22, w: 23, x: 24, y: 25, z: 26
    }
var maxValue = 0;
var maxLength = function(arr) {
    maxValue = 0;
    if(arr == null || arr.length == 0){
        return 0;
    }
    if(arr.length == 1){
        return arr[0].length;
    }
    var bitArr = [];
    for(let word of arr){
        let currentBitChar = 0, isQualified = true;;
        for(let ch of word){
            let bitChar =  (1 << charToNum[ch]);
            if((currentBitChar&bitChar) != 0){
                isQualified = false;
                continue;
            }
            currentBitChar = (currentBitChar | bitChar);
        }
        if(isQualified)
            bitArr.push(currentBitChar);
    }
    _maxLength(bitArr, 0, 0);
    return maxValue;
};

var bitCount = function (n) {
    let count = 0;
    if(n==0){
        return 0;
    }
    let mask = 1;
    for(let i=1; i<=26; i++){
        mask = (mask<<1)
        if((n&mask) > 0)
            count++;
    }
    return count;
}

var _maxLength = function(bitArr, bitMap, pos){
    if(pos == bitArr.length){
        maxValue = Math.max(maxValue, bitCount(bitMap));
        return;
    }
    _maxLength(bitArr, bitMap, pos+1);
    if((bitMap&bitArr[pos]) == 0){
        bitMap = bitMap | bitArr[pos];
        _maxLength(bitArr, bitMap, pos+1);
    }
}

Conclusion

That’s all folks! In this post, we solved LeetCode problem #1239. Maximum Length of a Concatenated String with Unique Characters

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!