MadeEasy Test Series: Algorithms - Dynamic Programming

Question

Consider two strings A = “abbaccda” and B = “abcaa” consider "x"be length of the longest common subsequence between A and B and “y” be the number of distinct such longest common subsequences between A and B. Then 10x+ 2y is ________.

Comments

44 is the answer

---

ok i m getting the same.

---

@nag.swarna

it is your responsibility that " Checking the question in GO before you are posting. "

 

it is duplicate of https://gateoverflow.in/230069/made-easy-test-series

Answer 1

By table method, it can solve but complexity is more..

One more method is Tree Method

A = "abbaccda" and B="abcaa"

1) LCS ( "abbaccd", "abca" ) +"a"

2) LCS ( " abbacc", "abca" ) + "a"

3) LCS( "abbacc", "abc")+"a" , LCS ( " abba", "abca" ) + "a"

4)  LCS( "abbac", "ab")+"ca"

5) "abca"

 

At step 3:- 

3) LCS ( " abba", "abca" ) + "a"

4) LCS ( " abb", "abc" ) + "aa"

5) "abaa"

 

X=4 and Y=2 ===> 10 x + 2^y = 10 (4) + 2² = 44

Answer 2

my aproach .verify it once 

 

it is 2^y ( it will be 2^2=4)

Comments

Thank you,I got it