Longest common substring | Dynamic programming

This video explains how to find the longest common substring as well as print the longest common substring. This is a very popular dynamic programming video which is frequently asked in programming interviews. The code for it is present below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: drive.google.c...

[@gourabbanerjee4152]

I believe I have gone through all the famous youtube channels explaining DSA. And I must say, the best explanation for each problem I find here. While I search for any problem, I have started looking whether TECH DOSE made any video on that or not, if yes, then I ignored all other channels blindly and I never disappointed. Thank you so much!!

[@techdose4u]

Welcome :)

[@amitis9632]

@@techdose4u I do the same, if I see a video from TECH DOSE I am done with my search.

[@ravi7264]

Same with me.

[@udayptp]

@@ravi7264 🔥

[@lakhwindersingh-qu6wj]

thank you tech dose. Finally someone explained this throughly

[@techdose4u]

Welcome :)

[@AtulKumarVermaOnline]

Most CZcamsrs just teach how it works and just go through the algorithm. Thank you for also teaching why it works and how to think about it.

[@Bhu22bhu22]

Nothing can be better than this, you really wanted to make things clear, simply awesome man.
Thank You and keep up the good work.

[@jhilikkundu3158]

Most underrated channel

[@techdose4u]

:)

[@mariocraft95]

Was able to use this algorithm to finish a spell checker assignment. Could not have done it near as well without this video!

[@atharvakulkarni2180]

Honestly, for beginners bottom up DP is not at all intuitive and your majority audience is beginner to medium level guys, so please try to explain DP problems using Top Down approach as well. BTW Very nice explanation. Thanks!

[@ashishm8850]

Dude, you have my respect, and my thanks! 🙏

[@techdose4u]

Welcome :)

[@EngWorld-nr2ww]

Nice and precise explanation than other available on youtube

[@damaroro]

YOUR VIDEO HELPS ME A LOT, THANKS SENSEI

[@prasad.patil12]

Such a detailed and clear explanation 👍

[@techdose4u]

Thanks

[@pavankumar.m1341]

Now i understood the logic of this dynamic programming

[@shagunlamba6481]

great explanation, recommending to everyone.

[@techdose4u]

Thanks

[@atefnazi753]

very well explained...want more DP solutions from you

[@geniusboys8204]

great explanation ! Thank you finally I understood it.....

[@techdose4u]

Nice :)

[@SammyTvMan]

Very well spoken, thank you

[@techdose4u]

Welcome :)

[@PrateekJesingh]

Good explanation of the dynamic programming bit but what was lacking was the intuition behind how you filled the table, please include that as well. You wouldn't expect anyone to just memorise the solution

[@shams_vai_360]

what is the difference between longest common subsequence and longest common substring?

[@chiragkamat4887]

Very nicely explained. Thank you :)

[@techdose4u]

Welcome :)

[@where3639]

Excellent video keep up the good work

[@techdose4u]

Thanks :)

[@prateeksrivastava9]

You made DP So Easy

[@techdose4u]

Thanks man :)

[@SZ-jw9my]

Excellent video, thank you!

[@techdose4u]

Welcome

[@adityagoswami6881]

Can you explain after getting the all diagonal number in dp table ,how to print the lcs strings

[@vemulacharanrayadhanush3110]

check this code
int main() {
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
string s,s1;
cin>>s>>s1;
vector dp(n+1,vector(m+1,0));
for(int i=1;i

[@BharadwajGiridhar]

Nice channel. I love your content!

[@soulehshaikh8799]

Easiest Explanation ever

[@adityapandey9639]

What will be the recursive approach of this Q?? We can't return 0 if it's character is not matching!

[@spartan5816]

Watch aditya verma YT channel. Thank me later

[@adityapandey9639]

@@spartan5816 bhai I have already watched his video it was nice bt he used to spend more time in relating the Q rather than developing the concept.. Didn't worked well in my case 🙃

[@sauravgsh16]

Great explanation. Can you also provide a space optimized solution for the same ?

[@techdose4u]

Will try to....actually too many important requested videos are already pending. So, i want to focus on important topics for now 😅

[@sauravgsh16]

@@techdose4u glad for the response .. will wait till you have time to upload one .. thanks ..

[@Pooh__7__]

Such an amazing video

[@techdose4u]

Thanks :)

[@yanamanagandlabhargavi4577]

Great explanation

[@sreekanththota2200]

sir,I like your Great explanation .....

[@techdose4u]

Thanks :)

[@JoseFranc]

Thank you so much

[@shubhamjaiswal7645]

explanation was good ...but what about memoization and recursion .... rather it would give TLE i know but you should firstly tell that n......

[@vallishreddy8263]

good explanation

[@techdose4u]

Thanks

[@ankitaverma2271]

Can you please tell me about [i-1] =[j-1]
Which index we are taking and how.?

[@techdose4u]

Because dp table is indexed from 1 (as index 0 in table means empty string) but the string position is always index from 0 (as index 0 means first character).

[@ankitaverma2271]

@@techdose4u Thank youu.
I got that.

[@ankitaverma2271]

As in the example you explained of there js no match in the characters then mark the dp row coloumn as zero.
Shouldn't we mark the max of row and coloumn??

[@techdose4u]

Max will be taken if we form subsequence where characters can be skipped but in this case you are matching substring, so whenever mismatch occurs, you cannot skip that character, you need to start from length 0 from the next character. This is the difference between subsequence and substring.

[@ShaliniNegi24]

thanks for the videos

[@techdose4u]

Welcome :)

[@andresnamm982]

You are awesome!

[@techdose4u]

Thanks :)

[@impatientgaming9868]

good one

[@bharathirv8479]

Hi, The code returns less than one value from the actual length of substring, so I return the value +1 (return lcs+1) now it returns the correct length. are my findings correct?

[@parnitasharma8898]

Great job

[@techdose4u]

Thanks

[@supernova7870]

Sir, do you have code for 0(N^3) approach , i solved it using 3 while loops , but the 3rd loop just execute for few statements , so i think its complexity is 0(N^2) .

[@MrThepratik]

that would be average case time complexity

[@praveenchouhan6388]

awesome explaination!!!!!!!!!!!!!! your way just super cool, thanks a lot!!!

[@techdose4u]

Welcome :)

[@shaziasamreen8584]

Sir can't we use the string Matching method.Brute force approach is n*m and there are String Matching algorithms that reduce the complexity can't we use them with some manipulations and find the longest common substring

[@osmantahir8659]

How to find a smallest number in the longest subsequence? in a dense subsequence. Dense subsequence means that the i+1 element should be less than or equal to 2 with the ith element in the subsequence

[@sakthim7160]

Why you are keeping all the elements as zero In the first row and column of a matrix? If any one of string doesn't contain any character, then we can simply say the result by using a single if conditions! And here 6x6 matrix is enough to perform what you have explained but why you are taking 7x7 matrix? Your space complexity is O(n1+1 * n2+1) complexity why? If I am using n1xn2 matrix that is 6x6 I have faced diagonal problem in matrix but I can solve it by putting a extra one condition! I want a explanation from your side kindly waiting for your reply! I think checking for the previous result that is previous diagonal only you are using the extra space

[@techdose4u]

If condition is costlier. The if condition will be compared for each of the 36 cells. If you just fill it with 0 then time complexity is heavily improved. Think about 100 by 100 matrix. You will be comparing if for all 10000 cells while you can simply put 199 zeroes when you already know they will be zero. 2nd reason is to make the formula work seamlessly and reduce the code complexity. So you gain both in terms of TIME and CODE complexity. I have explained why it will be 0 by the way :)

[@sakthim7160]

@@techdose4u thanks for your explanation😍you are almost responding to all of my comments. Thank you

[@techdose4u]

Welcome :)

[@RahulKumar-wf9xx]

What is the time complexity for the recursive Approach? is it O(2^(m+n)) ??

[@ibrahimshaikh3642]

Very good. Which whiteboard software u use

[@suryakiran2970]

super

[@techdose4u]

Welcome :)

[@AyushSingh-oq2fm]

does it have any recursive approach with memorisation??

[@techdose4u]

Yes it does

[@AyushSingh-oq2fm]

Please provide it's link I am struggling to come up with it's recursive logic

[@bismeetsingh352]

@9:46 , why does the position even matter? Eg. s0 = "acdghr" s1 = "cdghra", cdghr are at different positions but that is a valid answer.

[@techdose4u]

In LCS, order matters right ?

[@bismeetsingh352]

@@techdose4u order yes,positions no.

[@tejasghone5118]

Great Explaination !! Can you do the unique path question from leetcode? qs-62

[@techdose4u]

Sure....I think I have already done. Don't remeber 😅 If not then I will do it in future.

[@tejasghone5118]

@@techdose4u no u haven't done that coz from last month whenever i get stuck on some qs I search for your videos first😂

[@sayantaniguha8519]

Link?

[@sakthim7160]

One character can't be string know? Then how you can say a single character as subject?Or did we can say a single character is a substring?

[@techdose4u]

A single character is also a string actually. It's a string of length 1. Dont confuse with char and string datatypes. Think in general sense. A string can have no characters too (empty string).

[@sakthim7160]

@@techdose4u thank you

[@salmanfaries3064]

Would u have longest decreasing substring

[@techdose4u]

It's the same. Do LIS from the end.

[@sayantaniguha8519]

Recursive solution?
I don't care about TLE but need it for clear explanation

[@thatindianboy2817]

Any DFS Java solution?

[@chessmaster856]

Start with 0 n-1, then 1 n-1, then 0 n-2 etc. Stop at the first palindrome. Everything else will be smaller so no need to check. No dp required

[@harshareddy2772]

if that's the case please provide program

[@sais7065]

❤

[@techdose4u]

🙏🏼

[@575saisri4]

sir can u provide solutions of hackwithinfy round 1 2020 questions also plzz?

[@techdose4u]

I will try this weekend. Are the questions and editorials for the same are available?

[@saisrisai9649]

Yes sir.

[@techdose4u]

Okay...then I will try to find some time on weekend. But I can't guarantee.

[@coderpriyabrat3585]

💕💕💕💕💕💕💕💕💕💕

[@techdose4u]

;)

[@coderpriyabrat3585]

@@techdose4u nice explanation ❤️

[@techdose4u]

Thanks :)

[@madhurjyadas1471]

You stretch the video so long with some random unnecessary explanations.

[@techdose4u]

For some it may be unnecessary and for some it may be necessary. I explained assuming a beginner is watching. So people who already knows stuffs will feel its too long 😅 That's only my personal opinion though.

[@sreekanththota2200]

@@techdose4u
thats true bro....am a beginner

[@ruthwang9177]

@@techdose4u I find your explanation very helpful!

[@techdose4u]

Thanks

[@petarulev6977]

very bad explanation

[@huangCAnerd]

Absolute insanity that this solution TLEs on CodeSignal.