Test by Bikram | Algorithms | Test 2 | Question: 27

Question

The total number of LCS (Longest Common Subsequences) of $P = abcd123$  and $Q= badc321$ that can be formed are ______.

Answer 1

The LCS is of length 3. 

That means you have 3 blanks 

so now  

In First Blank - if you choose a then you cant choose b (vice versa) (So 2 options)

In Second Blank - if you choose c then you cant choose d (vice versa) (So 2 options)

In Third Blank - if you choose 1 then you cant choose 2,3 (vice versa) (So 3 options)

So total number of LCS = 2 * 2 * 3 = 12

Answer 2

The LCS are as follows:

ac1,ac2,ac3

ad1,ad2,ad3

bc1,bc2,bc3

bd1,bd2,bd3.

Comments

please tell me procedure of answer that u have written......

when i solve lcs length is 3 but after that what to do ...plzz tell how 12 is comming

---

You can easily find out LCS length: 3

Now you have three blanks: __ __ __

Now in last blank there will always be a number because all numbers are distinct. Hence, 3 ways.

Now, for the first 2 blanks:

we can fill them by various different combinations like: ba,bd,bc,ac,etc.

Now use hit and trial method to see if these letters exist in both the string given.

You'll get only 4:  bc,ac,bd,ad.

Hence: 4*3 = 12