The Gateway to Computer Science Excellence
+29 votes
3.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=$ ___.

in Algorithms by Veteran (105k points)
retagged by | 3.6k views
+2

LCS of length 4 ==> x=4

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

x+4y=34.

6 Answers

+32 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.
by Loyal (8.2k points)
edited by
+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?
+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???
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)

0
What made u think the LCS should end with either rr or qr ? Any logic ? Also why did u start considering 4 in the first place ??Couldn't understand your logic
+27 votes

I hope this helps. :)

by Boss (13.7k 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.
0
5th row and 6th column has two arrows which is wrong. Two arrows are possible only in case where we need to consider the previous adjacent cells but not previous diagonal cell. There will always be only one arrow in case of diagonal case.
+20 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
by Boss (25.6k 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

0
Here it's working because we had to select subsequences of length 4 from a total of 5. If we had to select 4 out of 6, there'd have been 15 possibilities.
+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

by Boss (11.6k points)
edited by
0
$pqrr,qpqr,qprr$ are three strings acc to figure
+1 vote
How to calculate the number of largest common subsequences..?
by Active (1k 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
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,737 questions
57,297 answers
198,265 comments
104,978 users