2.6k views

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=$ ___.

retagged | 2.6k views
+1

LCS of length 4 ==> x=4

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

x+4y=34.

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.
edited
+1
Do we always need to construct a table(Dynamic Programming Technique) ? or is there some other short method also...for calculating length of LCS?
+2
how do u get qqrr ?? is it in sequence ??
+1
we cant get qqrr..
0
Why should we dont considr permutation of rwo differnt qpqr

That way answer would become 44
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???

I hope this helps. :)

edited by
+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 ??
+1
Thank you @bharti ji. Typo is corrected.
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
0
No, we can't qqrr...as common.../// whr u r facing [email protected]
0
slight mistake ....
0
Ok..
0
Nice approach !! Although successful in certain cases only !
0

Thanks rahul sharma 5 for such a nice approach

0

There is $qprr$ in place of $aprr$ @rahul sharma 5

step 1- LCS(i,j) depends on LCS(i+1,j+1) when match else max{ LCS(i+1,j) and LCS(i,j+1)}

step 2- Starts at LCS(m,n) and fill by row,column or diagonal

step 3- When there is match then value of that cell 1+ LCS(i+1,j+1)  else step 1

Black Arrow - Fill columns and other arrow for backtracking

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

edited
0
$pqrr,qpqr,qprr$ are three strings acc to figure
How to calculate the number of largest common subsequences..?
+4

This will help you to calculate longest sub sequences by drawing a table and from there it will be easier for you to figure out number of longest subsequence

0
@Abhishek video is fine . But, still how to find the number of LCSs ??
0
@VS.Check my answer.It might give a little help
–1 vote
0
How

1
2