Amazon Coding Interview | Longest Common Substring Dynamic programming | EP6

longest common substring using dynamic programming - In this video, I have explained how to solve longest common substring problem in multiple ways.

longest common substring using recursion
longest common substring recursion with memorization or top-down approach
longest common substring using bottom-up approach

I have used FAST method to solve this DP problem.

Table of Content:
00:15 Problem statement
02:17 Longest common substring
03:00 Algorithm
06:54 Recurrence relation
08:00 Recursive solution
09:42 Recurrence tree
11:52 Top-down approach with memoization
13:30 Bottom-up approach/ DP solution
19:20 Demo

✚ Join our community ►

✅ Recommended playlists ►

📖 TOP 10 LEARNING RESOURCES

👋 Let’s Connect ►

#JAVAAID #lcsubstring #subsetsum #leetcode #javaAidTutorials #programming #dataStructures #algorithms #coding #competitiveprogramming #google #java #codinginterview #problemsolving #kanahaiyaGupta #hackerrankchallenges #facebook #amazon #oracle #linkedin

DISCLAIMER: These above-mentioned resources have affiliate links, which means if you buy one of the products from my links, I might receive a small commission without having no extra cost to you. This helps support the channel and allows us to continue to add more tutorial. Thank you for your support!

*NOTE: All above shared learning resources are best of my knowledge as I have personally read all except one Introduction to Algorithms.

[JavaAidTutorials]

Hey Every one,
If you find this tutorial helpful, please do not forget to like, comment, share
and It would be great if you can leave your feedback about the tutorial, as I have put a lot of hard work to make things easy for you.
Thanks ..!!

[pedestrian]

Finally someone who can explain things properly!!!


Sir your explanations are A++!!

[aditisharma]

Amazing! Only video that EXPLAINS what and why, not just writing the whole thing!
Came here after watching like 3 videos on lcs

[feafelhome]

Very nice! Thank you! Hadn't realized the use of 3-d array in top down approach compared to LCSubsequence where a 2-d cache is used.
This is probably the only problem where I find bottom-up approach easier to understand than top-down approach.
May I suggest one more thing: Could you possibly add an addendum to this video highlighting this use of 3-d vs 2-D array in top-down/bottom up approach? Or perhaps extend this video to inclue that explanation? That would make it a perfect and RARE complete coverage for this problem.
In any case, thank you!

[DBCatchx]

Your bottom up solution was awesome. Thank you!!

[jainneeraj]

Why do you have to take a cache of 3 dimensions instead of 2, is it because every level can be splitted into 3 recursive calls.

[hemantsood]

Your videos are awesome sir .Sir please make videos on problems regarding Queue in section of data structure in hackerrank platform

[rainMeToSleep]

Hey can you make videos on solving general stack based data structure solutions.(more like can you form a template?) You can pick these questions from Leetcode

[snehakavinkar]

Thank you for the awesome explanation!
Can you please explain how is the time complexity 3 raise to (m+n) at 9:42?

[VirajChokhany]

Sir why in longest common subsequence, we have an else condition for mismatch and not here?
I am slightly confused.

[durgaprasadd]

Really nice explanation. In LCSubStrA3 function, else potion of if(X[i-1] == Y[j-1]) is assigning ZERO to memo[i][j]. Verified with HARRY and SALLY, failed for me.
It's worked with below line:
memo[i][j] = max(memo[i][j-1], memo[i-1][j]);

[chandrashekhar]

Became the fan of your explanation!!.You are awesome man!!

[christianoronaldo]

I think that there is a slight mistake in the logic, you are using the same logic as longest common sub-sequence however there should be a difference, you should only call recursively when elements in both strings are equal and otherwise place a zero . please go through this comment and revisit your code .

[Mohammad-woyi]

Thanks for the awesome explanation.

Why the caching for memoization (method 2) is 3 dimensional array and for bottom up approach it's 2 dimensional array?
Is there a way to make the caching for (method 2) only a 2 dimensional array like the bottom-up approach?

[doruwyl]

Which is the time and space complexity for Solution 2A and 2B from your opinion?

[siddarthalk]

At 15:28, you mentioned "check the length of the previously calculated longest common substring"
This is wrong interpretation of the problem. We are not calculating longest common substring and storing in the table anywhere.
You should have told "check the length of previously calculated longest common SUFFIX"
Please correct if iam wrong

[manojb]

Sir where did I get source code for this problem

[irvinge]

why do you check the last character, and not the beginning?

[Navneetkumar-oscl]

In buttom up approach why did you write if(x[i-1]==y[j-1]) because at first when i and j is pointing to the first element then it would check whether (x[0]==y[0]) or not but our array starts from 1 1 here. Can't we just write if (x[i] ==y[j]) then memo[i] [j] =memo[i-1][j-1]+1;

[Mike-mwfu]

How do we determine correctly choosing two dimensional array or three dimensional array dp in top down approach?