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.com/open?id=1BWU...
Пікірлер: 125
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
3 жыл бұрын
Welcome :)
@amitis9632
3 жыл бұрын
@@techdose4u I do the same, if I see a video from TECH DOSE I am done with my search.
@ravi7264
2 жыл бұрын
Same with me.
@udayptp
2 жыл бұрын
@@ravi7264 🔥
thank you tech dose. Finally someone explained this throughly
@techdose4u
4 жыл бұрын
Welcome :)
Nothing can be better than this, you really wanted to make things clear, simply awesome man. Thank You and keep up the good work.
Most KZreadrs 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.
Was able to use this algorithm to finish a spell checker assignment. Could not have done it near as well without this video!
Dude, you have my respect, and my thanks! 🙏
@techdose4u
3 жыл бұрын
Welcome :)
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?
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!
Most underrated channel
@techdose4u
3 жыл бұрын
:)
great explanation ! Thank you finally I understood it.....
@techdose4u
3 жыл бұрын
Nice :)
Excellent video, thank you!
@techdose4u
3 жыл бұрын
Welcome
Very nicely explained. Thank you :)
@techdose4u
4 жыл бұрын
Welcome :)
Nice and precise explanation than other available on youtube
YOUR VIDEO HELPS ME A LOT, THANKS SENSEI
very well explained...want more DP solutions from you
Such a detailed and clear explanation 👍
@techdose4u
4 жыл бұрын
Thanks
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
great explanation, recommending to everyone.
@techdose4u
3 жыл бұрын
Thanks
Nice channel. I love your content!
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
3 жыл бұрын
that would be average case time complexity
Now i understood the logic of this dynamic programming
What is the time complexity for the recursive Approach? is it O(2^(m+n)) ??
Can you explain after getting the all diagonal number in dp table ,how to print the lcs strings
@vemulacharanrayadhanush3110
3 жыл бұрын
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
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
Very well spoken, thank you
@techdose4u
2 жыл бұрын
Welcome :)
Thank you so much
what is the difference between longest common subsequence and longest common substring?
Excellent video keep up the good work
@techdose4u
3 жыл бұрын
Thanks :)
Great explanation
What will be the recursive approach of this Q?? We can't return 0 if it's character is not matching!
@spartan5816
3 жыл бұрын
Watch aditya verma YT channel. Thank me later
@adityapandey9639
3 жыл бұрын
@@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 🙃
Great explanation. Can you also provide a space optimized solution for the same ?
@techdose4u
4 жыл бұрын
Will try to....actually too many important requested videos are already pending. So, i want to focus on important topics for now 😅
@sauravgsh16
4 жыл бұрын
@@techdose4u glad for the response .. will wait till you have time to upload one .. thanks ..
Such an amazing video
@techdose4u
3 жыл бұрын
Thanks :)
thanks for the videos
@techdose4u
3 жыл бұрын
Welcome :)
You are awesome!
@techdose4u
3 жыл бұрын
Thanks :)
good one
Very good. Which whiteboard software u use
does it have any recursive approach with memorisation??
@techdose4u
2 жыл бұрын
Yes it does
@AyushSingh-oq2fm
2 жыл бұрын
Please provide it's link I am struggling to come up with it's recursive logic
You made DP So Easy
@techdose4u
4 жыл бұрын
Thanks man :)
awesome explaination!!!!!!!!!!!!!! your way just super cool, thanks a lot!!!
@techdose4u
4 жыл бұрын
Welcome :)
Any DFS Java solution?
Can you please tell me about [i-1] =[j-1] Which index we are taking and how.?
@techdose4u
4 жыл бұрын
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
4 жыл бұрын
@@techdose4u Thank youu. I got that.
@ankitaverma2271
4 жыл бұрын
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
4 жыл бұрын
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.
Great job
@techdose4u
3 жыл бұрын
Thanks
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
good explanation
@techdose4u
3 жыл бұрын
Thanks
explanation was good ...but what about memoization and recursion .... rather it would give TLE i know but you should firstly tell that n......
Recursive solution? I don't care about TLE but need it for clear explanation
Would u have longest decreasing substring
@techdose4u
3 жыл бұрын
It's the same. Do LIS from the end.
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
4 жыл бұрын
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
4 жыл бұрын
@@techdose4u thank you
sir,I like your Great explanation .....
@techdose4u
4 жыл бұрын
Thanks :)
Great Explaination !! Can you do the unique path question from leetcode? qs-62
@techdose4u
4 жыл бұрын
Sure....I think I have already done. Don't remeber 😅 If not then I will do it in future.
@tejasghone5118
4 жыл бұрын
@@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
3 жыл бұрын
Link?
Easiest Explanation ever
sir can u provide solutions of hackwithinfy round 1 2020 questions also plzz?
@techdose4u
4 жыл бұрын
I will try this weekend. Are the questions and editorials for the same are available?
@saisrisai9649
4 жыл бұрын
Yes sir.
@techdose4u
4 жыл бұрын
Okay...then I will try to find some time on weekend. But I can't guarantee.
super
@techdose4u
Жыл бұрын
Welcome :)
❤
@techdose4u
Жыл бұрын
🙏🏼
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
4 жыл бұрын
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
4 жыл бұрын
@@techdose4u thanks for your explanation😍you are almost responding to all of my comments. Thank you
@techdose4u
4 жыл бұрын
Welcome :)
@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
3 жыл бұрын
In LCS, order matters right ?
@bismeetsingh352
3 жыл бұрын
@@techdose4u order yes,positions no.
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
11 ай бұрын
if that's the case please provide program
💕💕💕💕💕💕💕💕💕💕
@techdose4u
3 жыл бұрын
;)
@coderpriyabrat3585
3 жыл бұрын
@@techdose4u nice explanation ❤️
@techdose4u
3 жыл бұрын
Thanks :)
Absolute insanity that this solution TLEs on CodeSignal.
You stretch the video so long with some random unnecessary explanations.
@techdose4u
4 жыл бұрын
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
4 жыл бұрын
@@techdose4u thats true bro....am a beginner
@ruthwang9177
3 жыл бұрын
@@techdose4u I find your explanation very helpful!
@techdose4u
3 жыл бұрын
Thanks
very bad explanation