The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
2.2k 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=$ ___.

asked in Algorithms by Veteran (106k points)
retagged by | 2.2k views
+1

LCS of length 4 ==> x=4

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

x+4y=34.

6 Answers

+17 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.
answered by Loyal (8.1k points)
edited by
+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
+15 votes

I hope this helps. :)

answered by Boss (11.4k points)
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.
+12 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
answered by Boss (25.4k points)
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

+1 vote

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 

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

answered by Loyal (7.1k points)
edited by
0 votes
How to calculate the number of largest common subsequences..?
answered by Active (1.3k points)
+2

Go to above given link

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
34 should be the answer
answered by Active (3.5k points)
0
How
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,610 questions
48,608 answers
155,777 comments
63,776 users