LCS of length 4 ==> x=4

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

x+4y=**34**.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

+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.

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.

+20 votes

+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

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

+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

**Reference: - https://www.youtube.com/watch?v=xdA41xLxwuM&index=46&list=PLGdMwVKbjVQ8Ew7KUp65sRL9_k2_3xlKE**

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.5k
- Digital Logic 3k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.2k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 586
- Exam Queries 572
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,129 questions

53,252 answers

184,785 comments

70,506 users