Shortest way to form a string out of a subsequence of a string

Question

The task is taken from LeetCode (subscription required) -

From any string, we can form a subsequence of that string by deleting some number of characters (possibly no deletions).

Given two strings source and target, return the minimum number of subsequences of source such that their concatenation equals target. If the task is impossible, return -1.

Example 1:

Input: source = "abc", target = "abcbc"
Output: 2
// Explanation: The target "abcbc" can be formed by "abc" and "bc", which are subsequences of source "abc".

Example 2:

Input: source = "abc", target = "acdbc"
Output: -1
// Explanation: The target string cannot be constructed from the subsequences of source string due to the character "d" in target
// string.

Example 3:

Input: source = "xyz", target = "xzyxz"
Output: 3
// Explanation: The target string can be constructed as follows "xz" + "y" + "xz".

Note:

Both the source and target strings consist of only lowercase English letters from "a"-"z". The lengths of source and target string are between 1 and 1000.

My solution has space complexity of \$O(n)\$ and time complexity of \$O(n^2)\$ (I think...)

/**
 * @param {string} source
 * @param {string} target
 * @return {number}
 */
var shortestWay = function(source, target) {
    const map = new Map();
    for (let i = 0; i < source.length; i++) {
        if (map.get(source[i])) {
            const arr = map.get(source[i]);
            arr.push(i);
            map.set(source[i], arr);            
        } else {
            map.set(source[i], [i]);
        }
    }
    let occurrences = 0;
    for (let i = 0; i < target.length; i++) {
        const indexes = map.get(target[i]);
        if (indexes === void 0) return -1;
        occurrences++;
        let max = 0;
        indexes.forEach(index => {
            let j = 0;
            let ignore = 0;
            while(source[index + j + ignore] !== void 0) {
                if(target[i + j] !== source[index + j + ignore]) {
                    ignore++;
                } else {
                    max = Math.max(max, j++);
                }
            }
        });
        i += max;
    }
    return occurrences;
};

Answer 1

I believe your code is O(n^2*m), where n is the target and m is the source. Overall, though, I think there are a lot of readability improvements that could be made here by separating functions and renaming variables (j is a particularly bad contender).

// indexCharacters('hello')
// = {'h':[0],'e':[1],'l':[2,3],'o':[4]}
const indexCharacters = source => {
    const map = new Map();
    for (let i = 0; i < source.length; i++) {
        const char = source[i];
        if (!map.get(char)) map.set(char,[]);
        map.get(char).push(i);
    }
    return map;
}

// matchLength('abc','abeee') = 2
const matchLength = (source,target) => {
    let count = 0;
    for (let i=0;i<source.length;++i)
        if (target[count] === source[i])
            ++count;
    return count;
}

const shortestWay = (source, target) => {
    const all_character_indices = indexCharacters(source);
    let occurrences = 0;
    let targetIndex = 0;
    while (targetIndex < target.length) {
        const starting_indices = all_character_indices.get(target[targetIndex]);
        if (!starting_indices) return -1;
    
        const match_lengths = starting_indices.map(
            sourceIndex=>matchLength(
                source.substr(sourceIndex),
                target.substr(targetIndex)
            )
        );
    
        targetIndex += Math.max(...match_lengths);
        ++occurrences;
    }
    return occurrences;
};

console.log(shortestWay('abc','abcbc'))
console.log(shortestWay('abc','acdbc'))
console.log(shortestWay('xyz','xzyxz'))