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

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

LCS of length 4 ==> x=4

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


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$:





Now, check for matching sequences in second string, except for "$qqrr$" all are possible.
answered by Loyal (8.1k points)
edited by
Do we always need to construct a table(Dynamic Programming Technique) ? or is there some other short method also...for calculating length of LCS?
how do u get qqrr ?? is it in sequence ??
we cant get qqrr..
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
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 ??
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





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)
No, we can't common.../// whr u r facing [email protected]
slight mistake ....
Nice approach !! Although successful in certain cases only !

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: -

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)

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

@Abhishek video is fine . But, still how to find the number of LCSs ??
@VS.Check my answer.It might give a little help
–1 vote
34 should be the answer
answered by Active (3.5k points)

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
63,776 users