The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+26 votes
2.9k 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 (115k points)
retagged by | 2.9k views
+1

LCS of length 4 ==> x=4

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

x+4y=34.

6 Answers

+21 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.2k 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
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???
+20 votes

I hope this helps. :)

answered by Boss (12.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.
+14 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 (27.2k 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

0

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

+3 votes

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 Boss (11k points)
edited by
0
$pqrr,qpqr,qprr$ are three strings acc to figure
0 votes
How to calculate the number of largest common subsequences..?
answered by Active (1.4k points)
+4

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.6k 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
50,129 questions
53,252 answers
184,785 comments
70,506 users