Find minimum concat number of two strings

Question

Alice has two strings, initial and goal. She can remove some number of characters from initial, which will give her a subsequence of that string. A string with no deletions is still considered a subsequence of itself. Given these two strings, can you find the minimum number of subsequences of initial that, when appended together, will form goal?

Functions minimumConcat() has two parameters:

initial: the source string that you will get subsequences from goal: the target string that needs to be formed

Input Format For some of our templates, we have handled parsing for you. If we do not provide you a parsing function, you will need to parse the input directly. In this problem, our input format is as follows:

The first line is the initial String that we will be generating subsequences from The second line is the goal String to form Here is an example of the raw input:

abc bcbac

Expected Output Return the number of minimum possible subsequences of initial that can be appended together to form goal.

If there are no possible solutions, return -1. Example minimumConcat() Input #1

initial: "xyz"
goal: "xzyxz"

Output: 3

function minimumConcat(initial, goal) {
     //Put your code here.
    return 0;
}

Answer 1

Loop the initial string array to form the goal string array.

function minimumConcat(initial, goal) {
    initial = initial.split('');
    goal = goal.split('');
    let res,count=0;
    while(true){
        if(goal.length > 0){
            res = checkChar(initial,goal);
            if(false === res){
                return -1;
            }
        }else{
            return count;
        }
        goal = res;
        count++;
    }
}
function checkChar(initial,goal){
    let started = false;
    let foundIndex = 0;
    for(let i=0; i<initial.length; i++){
        if(initial[i] == goal[foundIndex]){
            started = true;
            foundIndex++;
        }
    }
    if(started){
        return goal.slice(foundIndex);
    }else{
        return false;
    }
}
console.log(minimumConcat('abc','bcbac'));

Answer 2

Here you go!

function minimumConcat(initial, goal) {
let result = 0;
let pattern = '';
let count1 = Array.apply(null, Array(26)).map(Number.prototype.valueOf, 0);
let count2 = Array.apply(null, Array(26)).map(Number.prototype.valueOf, 0);

initial.split('').forEach(c => {
    pattern = pattern + c
});
pattern = "^[" + pattern + "]*$";

if (!RegExp(pattern).test(goal)) return -1;

for (let i = 0; i < initial.length; i++) {
    count1[initial.charCodeAt(i) - 97]++;
}

for (let i = 0; i < goal.length; i++) {
    count2[goal.charCodeAt(i) - 97]++;
}

for (let i = 0; i < 26; i++) {
    result += Math.abs(count1[i] - count2[i]);
}

return result;
}

console.log(minimumConcat("abc", "bcbac"));

Answer 3

Since this looks like homework I won't give the solution right away, instead here is a suggestion on how to solve it:

I think the hardest part is finding all the sub-strings if you are using Python that's simplified by itertools as mentioned here.

Edit, I didn't notice the javascript tag, you can get the substring set, without a library, with a couple of for loops.

After having all combinations from initial you can sort them to have the longest first. And then go one by one removing them from goal. Counting every time you remove. If, after iterating over all sub-strings, goal is not an empty string then no subsequence of initial can construct goal.