Algorithm to calculate maximum possible length of a String

user_11068392 0
Viewed 228

Problem:

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

Examples:

Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
Maximum length is 4.

Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible solutions are "chaers" and "acters".

My solution:

var maxLength = function(arr) {
    if(!arr || arr.length === 0)    return 0;
    
    let word = "";
    arr.sort((a,b) => b.length - a.length);
    let set = new Set();
    
    const removeFromSet = (str) => {
        for(let i=0; i<str.length; i++) {
            set.delete(str[i]);
        }
    }
    
    const isInSet = (str) => {
        for(let i=0; i<str.length; i++) {
            if(set.has(str[i])) {
                removeFromSet(str.substring(0, i));
                return true;
            }
            else 
                set.add(str[i]);
        }
        return false
    }
    
    for(let i=0; i<arr.length; i++) {
        if(!isInSet(arr[i])) {
            word += arr[i];
        }
    }
    
    return word.length;
};

It fails for the input: ["ab","cd","cde","cdef","efg","fgh","abxyz"] It should return 11, but my solution returns 9.

I know that my solution is calculating: "abxyzcdef" and it should be: "abxyzfghcde". Does anyone know what I am doing wrong?

Thanks

set arrays javascript string
2 Answers

Hole algorithm is recursivly, starting with only the string-array. If the second parameter str is not defined than it's setted to an empty strin (only at start).
Iterate through the string-array look if there is a builded string. If so than split the new teststring in chars and look if there exists at least one char (with Array#some) that is included in the builded string. If this condition is as well true than the string would not be contain unique chars so we can continue. Otherwise this is till now a possible sollution.
Now take the array and remove all the teststrings which have been tried (included the actual tested) because testing with them isn't usefull. Call the algorithm itself recursivly with shortened string-array and the string extended with the actual teststring.
Look if the length of the acual teststring plus the return value of recursiv call is greater than maximum than actualisize it.
After iterateing through all testrings from the array return the maximum length from an allowed string.

Extended: I check at start all strings with Array.filter for words with multiple same chars so e.g. 'abba' will not be tested.

function maxLength(array, str) {
       if (str === undefined) {
           str = '';
           array = array.filter(elem => elem.split('').every((char, key) => !(elem.slice(key+1)).includes(char)));
    };
    array = array.filter(elem => elem.split('').every((char, key) => !(elem.slice(key+1)).includes(char)));
    let max=0;
    for (let i=0; i<array.length; i++) {
        let test= array[i];
        if (str.length && test.split('').some(char => str.includes(char))) {
             continue;
        } else {
            let len = test.length + maxLength(array.slice(i), str + test);
            if (len>max) max=len;
        }
    }
    return max;
}

console.log( maxLength(["un","iq","ue"]) );
console.log( maxLength(["cha","r","act","ers"]) );
console.log( maxLength(["ab","cd","cde","cdef","efg","fgh","abxyz"]) );
console.log( maxLength(["yy","bkhwmpbiisbldzknpm"]) );

user_53245110

I found your logical fault: You only look straight forward and if one string not match you leave this one out and testing the next and go on like this.
But if one string matches you never look if possible another would be better.

Explanation:
I will explain it a little more. These are your sorted strings for testing:

["abxyz", "cdef", "cde", "efg", "fgh", "ab", "cd"]

You tried these combinations(first the tested good string and second your actual candidate) and afterwardes result for testing:

abxyz => ok
abxyz cdef => ok
abxyz cdef cde => false
abxyz cdef efg => false
abxyz cdef fgh => false
abxyz cdef ab => false
abxyz cdef cd => false

So your max-length is 9 (choose the first and the second string). But the solution abxyz cde fgh you don't take a look on it. For this you had to look instead of cdef for the shorter cde which is in combination with fgh the solution.

This is only the explanation why this don't work but not how you can solve it ;).

user_53245110
Related