Algorithm : concatenate sub-string based on their first and last characters [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 9 years ago.

Improve this question

Numbers of strings are given,

We need to join all strings to make single valid string.

All the characters of string are lowercase letters [a-z].

Valid string means :

• We need to concatenate sub-string where the last letter of a sub-string match the first one of another one (example aa ab => becomes aaab // aa ba => becomes baaa)

• All the same characters of the string should be adjacent.

Calculate how many numbers of combinations are possible to make valid string.

Example:

input :

array(aa, ab, bc, aa)

desired output :

This expression got two possible combinaison.
(since "aa aa ab bc" is deferent from "aa aa ab bc", cause there is two aa, and they must not be considered equals)

My efforts :-

I just know its a graph problem. (Connected component Problem).

Please help me so that I can build this algorithm.

I need your guidance, not exact algorithm. So that I can myself build the algorithm

Answer 1

How i'd handle this one :

Let's declare 2 variables :

int factorials_quotient = 1;
int solution_count = 0;

As an example, il will use string : abc cme eqk aa a bb b, since it it the trickiest case

FIRST : identify the 'concat' strings.

Exemple : abc cme eqk aa a bb b

Since 'abc cme eqk' string only have a unique order, you MUST concatenate them and consider it as a unique string : abccmeeqk aa a bb b. (For each concatenation, if the first letter equals the last letter on the substring, you got a exeption case, you must handdle it).

SECOND: identify the 'factorials' strings.

Exemple : abccmeeqk aa a bb b We are looking for two or more string containing the same characters like : aa a & bb b (DO NOT count 'abcmeeqk' since it contains char different from a).

For each of these string multiply factorials_quotient by n!

In our case, we first got aa a, since we have 2 string (a and aa) we multiply factorials_quotient by factorial(2), then the same for bb b. our factorials_quotient now equals 1 * 2! * 2! = 4.

Then concatenate aa to a and bb to b.

We now got : abccmeeqk aaa bbb.

THIRD : try to concatenante the factorials and the concats if it is possible.

Exemple we not have abccmeeqk aaa bbb.

Since abccmeeqk start with a qe have to put aaa in front of, we now got : aaaabccmeeqk bbb

FOUR : get your result

solution_cuount = factorials_quotient * factorial(number of sub-string in our string)

In our case : aaaabccmeeqk bbb we got 2 sub-string.

solution_count = 4 * 2! = 4 * 2= 8 solutions :

Possible solutions :

aa  a   abc cme eqk bb  b
aa  a   abc cme eqk b   bb
a   aa  abc cme eqk bb  b
a   aa  abc cme eqk b   bb

bb  b   aa  a   abc cme eqk
b   bb  aa  a   abc cme eqk
bb  b   a   aa  abc cme eqk
b   bb  a   aa  abc cme eqk

Array step by step :

STEP 0: (at start)

array(
    "aa",
    "a",
    "abc",
    "cme",
    "eqk",
    "bb",
    "b"
)

STEP 1:

array(
    "aa",
    "a",
    "abccmeeqk",
    "bb",
    "b"
)

STEP 2:

array(
    "aaa",
    "abccmeeqk",
    "bbb"
)

STEP 3:

array(
    "aaaabccmeeqk",
    "bbb"
)

STEP 4:

you got your result