DP - 7: Longest common Substring

[@naamhaii]

can be solve it using top down approach

[@anirbanchakraborty690]

Your videos are great! very detailed and clear cut! please keep making such videos :)

[@CodingSimplified]

Thanks Anirban for your feedback. Keep Watching.

[@electronicseverywhere204]

Send me recursive code of this q , i understood your explanation :)

[@surajgrandhi6742]

Very good explanation sir, Best DP series , will try to solve remaining

[@CodingSimplified]

Thanks Suraj for your nice feedback. Keep Watching.

[@pratyushvatsa7490]

3:20 - That is the longest common *subsequence*

[@sharuk3545]

One of the best solution on youtube

[@CodingSimplified]

Thanks for your nice feedback. Keep Watching.

[@omprakashsharma9767]

This is best solution so far i seen gr8 work bro :)

[@CodingSimplified]

Glad to hear that. Thanks.

[@raman-jn6yt]

Hi, I need one help. In the previous problems you explained, our answer is generally stored in the last cell of our solution matrix i.e. sol[m][n]. But in this problem, we have to find maxLCS from our solution 2d-matrix Can you explain that how we decide this?

[@CodingSimplified]

Decision is made depending on the requirement & storage we've. In this question, we can't apply the same as sol[m][n], as max LCS can be at any place, so whenever there's change we're updating maxLCS & returning as answer. Thanks.

[@coollatchu]

Can you please elaborate why we need to fill 0's in first row and in first column?

[@shankysays]

Base condition

[@aj9706]

Sir could u explain how to convert recursive dp to bottom up dp iterative version. Recursive solutionz are expensive in hackerearth contests due to stack over flow. Converting to iterative is quite difficult requires lot of practice.

[@ram-pc4wk]

Aditya Verma channel

[@ram-pc4wk]

Here u can find

[@ujjwaljain9780]

Sir why we are not initialised the first row and column ,u directly started with I=1 and j=1.wht about I=0 and j=0???

[@dandesatvikreddy4424]

that comes in picture ..he just did if(n==0||m==0)just make it as zeros ..... the first row and first column is n=0&m=0..

[@vastauine6398]

you could have used memoization and changed recursion complexity to O(MN)

[@dipteshkumar7247]

can you please provide memorization source code?

[@himanshubansal6425]

top to bottom dp solution is missing.

[@raman-jn6yt]

Hi, Would you please highlight purpose of adding 'countOfLCS' in method parameter? I am trying below solution. Would you let me know what is the problem here? private static int lcsRec(String s1, String s2, int m, int n) { /** base condition - if any string is empty, there is no common substring so return 0 */ if (m < 0 || n < 0) return 0; int lcs1, lcs2, lcs3; if (s1.charAt(m) == s2.charAt(n)) lcs1 = 1 + lcsRec(s1, s2, m-1, n-1); else lcs1 = lcsRec(s1, s2, m-1, n-1); lcs2 = lcsRec(s1, s2, m-1, n); lcs3 = lcsRec(s1, s2, m, n-1); return Math.max(Math.max(lcs1, lcs2), lcs3); } Thanks

[@CodingSimplified]

'countOfLCS' is representing length of Longest Common Substring. - Try with some example like str1 = "abc" & str2 = "abc" - Another example str1 = "abc" & str2 = "ebc" Try to run pseudo code on these example for better understanding.

[@shobhitgarg6897]

DO you get the answer for this problem?Please help!

[@aj9706]

It's wrong ur doing longest common subsequence

[@BlokeBritish]

yeh 'subeestring' kya hai

[@ahmedsamir1601]

Great Keep going bro

[@CodingSimplified]

Thanks. Keep Watching.