LCS of length 4 ==> x=4

LCS={qpqr,qprr,pqrr} ==>y=3

x+4y=**34**.

35 votes

Consider two strings $A$=*"qpqrr"* and $B$=*"pqprqrp"*. Let $x$ be the length of the longest common subsequence *(not necessarily contiguous) *between $A$ and $B$ and let $y$ be the number of such longest common subsequences between $A$ and $B$. Then $x +10y=$ ___.

34 votes

Best answer

Answer is $34$.

In first string, if we want to get $4$ as maximum length then LCS should end with either "$rr$" or "$qr$".

Only $4$ combinations are possible for LCS with length $4$:

"$qpqr$", "$qqrr$","$pqrr$","$qprr$"

Now, check for matching sequences in second string, except for "$qqrr$" all are possible.

In first string, if we want to get $4$ as maximum length then LCS should end with either "$rr$" or "$qr$".

Only $4$ combinations are possible for LCS with length $4$:

"$qpqr$", "$qqrr$","$pqrr$","$qprr$"

Now, check for matching sequences in second string, except for "$qqrr$" all are possible.

2

Do we always need to construct a table(Dynamic Programming Technique) ? or is there some other short method also...for calculating length of LCS?

0

plz clearify

Here in question it is explicitly mentioned (Not necessarily Contiguous) but if Only Longest Common Subsequence is mentioned what should be our approach?Will it be same???

Here in question it is explicitly mentioned (Not necessarily Contiguous) but if Only Longest Common Subsequence is mentioned what should be our approach?Will it be same???

0

see 1st 5 minutes in this video -

here he introduced a technique to tackle.

but that is not always reliable in exam hall.

my doubt is - how to solve this in 3 minutes(using table & backtracking it's quite difficult to do fast)

34 votes

1

PLEASE Check in 5th row 4th colum their is a match of R and you have not incremented it ... but still you are getting through answer ... how ??

23 votes

Its a big problem if we solve it with DP or recursion.So we should use some intuition to get answer.

A=5 length and B= 7 length.

Maximum x can be 5 but 5 is not possible so try with 4 and we can easily find that 4 is satisfying for x.Now we need to find y.Here we know x=4 ,so let us write all the 4 length subsequences of A.As A is 5 length and we need 4 length so remove 1 character at a time and get the subsequence.

1. qpqr

2.qpqr

3.aprr

4.qqrr

5.pqrr

Now look for these in B and we will see except qqrr all are satisfying.So y=4 ,but 1 and 2 are same ,so y=3.

Now x+10y=34

A=5 length and B= 7 length.

Maximum x can be 5 but 5 is not possible so try with 4 and we can easily find that 4 is satisfying for x.Now we need to find y.Here we know x=4 ,so let us write all the 4 length subsequences of A.As A is 5 length and we need 4 length so remove 1 character at a time and get the subsequence.

1. qpqr

2.qpqr

3.aprr

4.qqrr

5.pqrr

Now look for these in B and we will see except qqrr all are satisfying.So y=4 ,but 1 and 2 are same ,so y=3.

Now x+10y=34

4 votes

$\text{Step 1}:$ $LCS(i,j)$ depends on $LCS(i+1,j+1)$ when match else $max\{ LCS(i+1,j)\space and\space LCS(i,j+1)\}$

$\text{Step 1}:$ Starts at $LCS(m,n)$ and fill by row,column or diagonal

$\text{Step 1}:$ When there is match then value of that cell $1+ LCS(i+1,j+1)$ else $\text{Step 1}$

Black Arrow - Fill columns and other arrow for backtracking

so $x= 4 $and $y = 3 $

$x+10y = 4+10 * 3 = 34 $

Reference: - https://www.youtube.com/watch?v=xdA41xLxwuM&index=46&list=PLGdMwVKbjVQ8Ew7KUp65sRL9_k2_3xlKE