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!!
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!
@@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 🙃
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
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?
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
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).
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??
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.
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) .
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
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).
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
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 :)
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.
![VICTOR Denmark Open 2024 | An Se Young (KOR) [1] vs. Gregoria Mariska Tunjung (INA) [5] | SF](http://i.ytimg.com/vi/Y3QEyCih85s/mqdefault.jpg)
![GEEK TIMË [OFFICIAL AUDIO]](http://i.ytimg.com/vi/ry-6RvkH880/mqdefault.jpg)
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!!
Welcome :)
@@techdose4u I do the same, if I see a video from TECH DOSE I am done with my search.
Same with me.
@@ravi7264 🔥
Nothing can be better than this, you really wanted to make things clear, simply awesome man.
Thank You and keep up the good work.
thank you tech dose. Finally someone explained this throughly
Welcome :)
Most RUclipsrs 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!
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
:)
YOUR VIDEO HELPS ME A LOT, THANKS SENSEI
Nice and precise explanation than other available on youtube
Dude, you have my respect, and my thanks! 🙏
Welcome :)
Now i understood the logic of this dynamic programming
what is the difference between longest common subsequence and longest common substring?
Very well spoken, thank you
Welcome :)
Such a detailed and clear explanation 👍
Thanks
very well explained...want more DP solutions from you
great explanation, recommending to everyone.
Thanks
great explanation ! Thank you finally I understood it.....
Nice :)
Can you explain after getting the all diagonal number in dp table ,how to print the lcs strings
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
does it have any recursive approach with memorisation??
Yes it does
Please provide it's link I am struggling to come up with it's recursive logic
Excellent video keep up the good work
Thanks :)
Nice channel. I love your content!
What will be the recursive approach of this Q?? We can't return 0 if it's character is not matching!
Watch aditya verma YT channel. Thank me later
@@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 🙃
Easiest Explanation ever
Great explanation
Very nicely explained. Thank you :)
Welcome :)
Excellent video, thank you!
Welcome
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
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?
sir,I like your Great explanation .....
Thanks :)
Such an amazing video
Thanks :)
Very good. Which whiteboard software u use
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
Any DFS Java solution?
Great explanation. Can you also provide a space optimized solution for the same ?
Will try to....actually too many important requested videos are already pending. So, i want to focus on important topics for now 😅
@@techdose4u glad for the response .. will wait till you have time to upload one .. thanks ..
explanation was good ...but what about memoization and recursion .... rather it would give TLE i know but you should firstly tell that n......
Would u have longest decreasing substring
It's the same. Do LIS from the end.
Can you please tell me about [i-1] =[j-1]
Which index we are taking and how.?
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).
@@techdose4u Thank youu.
I got that.
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??
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.
Thank you so much
good explanation
Thanks
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) .
that would be average case time complexity
You made DP So Easy
Thanks man :)
What is the time complexity for the recursive Approach? is it O(2^(m+n)) ??
thanks for the videos
Welcome :)
Great job
Thanks
You are awesome!
Thanks :)
good one
awesome explaination!!!!!!!!!!!!!! your way just super cool, thanks a lot!!!
Welcome :)
Recursive solution?
I don't care about TLE but need it for clear explanation
@9:46 , why does the position even matter? Eg. s0 = "acdghr" s1 = "cdghra", cdghr are at different positions but that is a valid answer.
In LCS, order matters right ?
@@techdose4u order yes,positions no.
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
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?
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).
@@techdose4u thank you
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
if that's the case please provide program
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
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 :)
@@techdose4u thanks for your explanation😍you are almost responding to all of my comments. Thank you
Welcome :)
super
Welcome :)
Great Explaination !! Can you do the unique path question from leetcode? qs-62
Sure....I think I have already done. Don't remeber 😅 If not then I will do it in future.
@@techdose4u no u haven't done that coz from last month whenever i get stuck on some qs I search for your videos first😂
Link?
sir can u provide solutions of hackwithinfy round 1 2020 questions also plzz?
I will try this weekend. Are the questions and editorials for the same are available?
Yes sir.
Okay...then I will try to find some time on weekend. But I can't guarantee.
❤
🙏🏼
💕💕💕💕💕💕💕💕💕💕
;)
@@techdose4u nice explanation ❤️
Thanks :)
Absolute insanity that this solution TLEs on CodeSignal.
very bad explanation
You stretch the video so long with some random unnecessary explanations.
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.
@@techdose4u
thats true bro....am a beginner
@@techdose4u I find your explanation very helpful!
Thanks