mkmeden's blog

By mkmeden, history, 2 years ago, In English

https://www.hackerrank.com/challenges/tutzki-and-lcs/problem

I ve been trying to solve this for hours and could'nt find any understandable online solution, Can anyone explain the logic and code behind this problem.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

You just calculate the $$$LCS$$$ as you do.
Let $$$dp1[i][j]$$$ denotes the $$$LCS$$$ of the suffix starting from $$$ith$$$ and $$$jth$$$ index of string $$$a$$$ and $$$b$$$ respectively.
And $$$dp2[i][j]$$$denotes the $$$LCS$$$ of the prefix till $$$ith$$$ and $$$jth$$$ index of string $$$a$$$ and $$$b$$$ respectively.

Now assume we are adding a character before $$$ith$$$ index of string $$$a$$$ to match it with $$$jth$$$ index of string $$$b$$$. Think of the condition for this pair of indexes to contribute to the answer.

Condition

If we implement that condition directly, then it will overcount. Think why is it so?

Reason
How to fix it?
Code
  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Thank you so much brother. I understood your explanation.

    My Code