# GATE2014-2-37

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

retagged
4

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
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?
3
how do u get qqrr ?? is it in sequence ??
2
we cant get qqrr..
0
Why should we dont considr permutation of rwo differnt qpqr

That way answer would become 44
–1
0
How
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)

1
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
0
I have tried to code it. If there some bug, plz let me know or fix it.
https://ideone.com/AV0kkF

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.
1
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.
0
any easier method to find number of such sequences apart from this?
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

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.

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

edited
0
$pqrr,qpqr,qprr$ are three strings acc to figure
1 vote
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

I got the answer while doing like this at the first attempt. Is this a valid method.

## Related questions

1
4.8k views
Suppose you want to move from $0$ to $100$ on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers $i,\:j \:\text{with}\: i <j$. Given a shortcut $(i,j)$, if you are at position $i$ on the ... $15$. Let $y$ and $z$ be such that $T(9) = 1 + \min(T(y),T(z))$. Then the value of the product $yz$ is _____.
Suppose $P, Q, R, S, T$ are sorted sequences having lengths $20, 24, 30, 35, 50$ respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.
Consider the function func shown below: int func(int num) { int count = 0; while (num) { count++; num>>= 1; } return (count); } The value returned by func($435$) is ________