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!
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
@@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 🙃
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
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) .
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
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?
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.
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 🔥
thank you tech dose. Finally someone explained this throughly
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 UA-camrs 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!
Most underrated channel
:)
Dude, you have my respect, and my thanks! 🙏
Welcome :)
Nice and precise explanation than other available on youtube
Now i understood the logic of this dynamic programming
YOUR VIDEO HELPS ME A LOT, THANKS SENSEI
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!
very well explained...want more DP solutions from you
Such a detailed and clear explanation 👍
Thanks
great explanation, recommending to everyone.
Thanks
Very well spoken, thank you
Welcome :)
great explanation ! Thank you finally I understood it.....
Nice :)
Excellent video keep up the good work
Thanks :)
Easiest Explanation ever
Very nicely explained. Thank you :)
Welcome :)
Excellent video, thank you!
Welcome
Nice channel. I love your content!
@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.
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
what is the difference between longest common subsequence and longest common substring?
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
Such an amazing video
Thanks :)
sir,I like your Great explanation .....
Thanks :)
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 🙃
You made DP So Easy
Thanks man :)
Great explanation
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 ..
good explanation
Thanks
thanks for the videos
Welcome :)
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
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
awesome explaination!!!!!!!!!!!!!! your way just super cool, thanks a lot!!!
Welcome :)
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.
Great job
Thanks
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
You are awesome!
Thanks :)
Very good. Which whiteboard software u use
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
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
What is the time complexity for the recursive Approach? is it O(2^(m+n)) ??
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?
explanation was good ...but what about memoization and recursion .... rather it would give TLE i know but you should firstly tell that n......
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
Recursive solution?
I don't care about TLE but need it for clear explanation
good one
Any DFS Java solution?
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?
super
Welcome :)
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 :)
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.
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
very bad explanation