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;
}

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;
}

• javascript

• 3 Looks like a homework. Have you tried solving it yourself? – ibrahim mahrir Commented Nov 11, 2019 at 18:20
• Yes. But, not getting nearby it's solution. – praveen-me Commented Nov 11, 2019 at 18:21
• 4 Perhaps you can show your work and discuss where you are stuck. Questions which are simply copy-pastes of homework problems tend to be heavily downvoted and rapidly closed. – John Coleman Commented Nov 11, 2019 at 18:28
• How did you solve it? – Tim Commented Nov 12, 2019 at 17:08
• @praveen-me did you find way to solve this – Praveen Soni Commented Mar 5, 2020 at 13:35

8 Answers 8

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'));

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"));

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.

This answers your question using Java

public static int minimumConcat(String initial, String goal) {
        HashSet<Character> set = new HashSet<>();
        for(char c : initial.toCharArray()) set.add(c);
        for(char c : goal.toCharArray()) {
            if(!set.contains(c)) return -1;
        }
        int j = 0, result = 0;
        for(int i = 0; i < goal.length();) {
            char c = goal.charAt(i);
            while(j < initial.length() && initial.charAt(j) != c) j++;
            if(j == initial.length()) {
                j = 0;
                result++;
            } else {
                j++;
                i++;
            }
        }
        result++;
        return result;
   }

Here is what I've done with python

def minimumConcat(initial, goal):
   #verify that goal has all character of initial
    res = 0
    for i in goal:
        if i in initial:
            pass
        else:
            res=-1;

    if res != -1:
        while goal!="":
            a = removefirstGreatestSubstring(initial,goal)
            goal=a["goal"];
            if a["has"] ==True :
                res=res+1
        #find the greatest concat 
    print(res)

def removefirstGreatestSubstring(initial,goal):
    has_subtring = False
    start = 0
    for car in initial:
        if car == goal[start]:
            has_subtring= True
            start = start+1
            finalgoal=goal[start:]
    return {"goal": finalgoal, "has":has_subtring}

initial = "abc"
goal = "bcbac"
b = minimumConcat(initial, goal)

I've made it using a different approach with regular expressions.

Here a clean version of the code:

"use strict";

// Solution:
function minimumConcat(initial, goal) {

    let result = -1;
    let goal_slice = goal;
    let exp = "", sub = "";
    let initial_concat =  "";
    let matches = 0, count = 0; 
    let initial_arr = initial.split('');

    for(let i = 0 ; i<initial_arr.length; i++){
        for(let j = initial_arr.length ; j>i+1; j--){
            sub = initial.slice(i,j);
            exp = new RegExp(sub,"ig");
            matches = (goal_slice.match(exp) || []).length; 
            if(matches>=1) {
                count +=matches;
                initial_concat+=sub.repeat(matches);
                goal_slice = goal_slice.slice((goal_slice.lastIndexOf(sub)+sub.length));
            }
        }      
    }

    result = (initial_concat==goal)? count : result;
    return result; 
}

// Test cases:
let test_cases = [
    {initial:"abc", goal: "abcbc"},  // expected result  2
    {initial:"abc", goal: "acdbc"},  // expected result -1
    {initial:"bcx", goal: "bcbcbc"}, // expected result  3
    {initial:"xyz", goal: "xyyz"},   // expected result  2
]

// Running the tests:
test_cases.forEach(function(item,index){
    console.log(minimumConcat(item.initial, item.goal));
});

Also, I've included a debug flag to turn on/off console.log messages in order to anybody could easily understand what is happening on each iteration cycle.

"use strict";

// Shwitch for debugging:
const debug = true;

// Solution:
function minimumConcat(initial, goal) {

    let exp = "";
    let sub = "";
    let match = 0;
    let count = 0;
    let result = -1;
    let goal_slice = goal;
    let initial_concat =  "";

    let initial_arr = initial.split('');

    for(let i = 0 ; i<initial_arr.length; i++){
        for(let j = initial_arr.length ; j>i+1; j--){
            sub = initial.slice(i,j);
            exp = new RegExp(sub,"ig");
            match = (goal_slice.match(exp) || []).length; 
            if(match>=1) {
                count +=match;
                initial_concat+=sub.repeat(match);
                goal_slice = goal_slice.slice((goal_slice.lastIndexOf(sub)+sub.length));
            }

            if(debug){
                console.log("-----------------------------");
                console.log("   i:", i, " - j:", j);
                console.log("   exp:", exp);
                console.log("   goal:", goal);
                console.log("   goal_slice:", goal_slice);
                console.log("   match:",match);  
            }    
        }      
    }

    result = (initial_concat==goal)? count : result;

    if(debug){
        console.log("---RESULTS:--------------------------");
        console.log("count:",count);
        console.log("goal vs initial_concat: ", goal, " - ", initial_concat);
        console.log("result: ", result);
    }

    return result; 
}

// Test cases:
let test_cases = [
    {initial:"abc", goal: "abcbc"},  // expected result  2
    {initial:"abc", goal: "acdbc"},  // expected result -1
    {initial:"bcx", goal: "bcbcbc"}, // expected result  3
    {initial:"xyz", goal: "xyyz"},   // expected result  2
]

// Running the tests:
test_cases.forEach(function(item,index){    
    if(debug){
        console.log("-----------------------------");
        console.log("TEST CASE #",index,":");
        console.table(item);
    }
    minimumConcat(item.initial, item.goal);
});

here is in php

public function index()
{

    $init="abc";
    $goal="abacabacabacacb";
    $res=$this->minimum($init,$goal);

}

public function check($inital,$goal){
    $inital=str_split( $inital);
    $goal=str_split( $goal);


    for($i=0;$i<sizeof($goal);$i++){
        if(!in_array($goal[$i],$inital)){
            return -1;
        }
    }
    return 0;

}
public function minimum($inital,$goal){
    $res=$this->check($inital,$goal);
    if($res==-1){
        return -1;
    }
    $counter=0;
    $c=0;
    $inital=str_split( $inital);
    $goal=str_split( $goal);


    for($i=0;$i<sizeof($goal);$i++){
        for($j=0;$j<sizeof($inital);$j++){

            if(($i+$c)<sizeof($goal)){

                echo " ".$i." > ".$j." > ".$c."   /// ";
                if($goal[$i+$c]==$inital[$j]){
                    $c+=1;
                }
            }

        }

        $counter+=1;
         if(($i+$c)>=sizeof($goal)){
            break;
        } 
        $c=$c-1;

    }


    return $counter;
}

Here is my python solution

def check_char(initial, goal):
    N = len(initial)
    started = False
    found_index = 0
    for i in range(N):
        if (initial[i] == goal[found_index]):
            started = True
            found_index += 1
    if(started):
        return goal[found_index:]
    else:
        return '-'


def minimumConcat(initial, goal):
    res = 0
    count = 0
    while(True):
        if( len(goal) > 0 ):
            res = check_char(initial, goal)
            if(res == '-'):
               print(-1)
               break;
        else:
            print(count)
            break;

        goal = res
        count += 1

initial = input()
goal = input()
minimumConcat(initial, goal)