Those who are wondering why did we put '0' in those places where the characters didn't match, since in the longest common sub sequence we took the max of the two adjacent cells instead of putting '0'. The biggest difference between longest common sub sequence and sub string is the way we interpret dp[i][j]. for Longest common sub sequence, dp[i][j] means the longest common sub sequence between "starting from 0 to i for string s1" and "starting from 0 to j in string s2",. In contrast, for Longest common sub string, dp[i][j] means the longest common sub string between S1 and S2 "starting from i and j" This is very crucial to understand cause this is making all the difference. For sub sequence we are always starting from index 0 and finding out the longest value possible, for sub string we are always starting from the current index and iteratively increasing the value. Since for sub string they need to be consecutive that is why whenever we are finding there's a mismatch we are saying 0 cause starting from i, j so far we have not found any sub string. hope this helps.
Your videos are pretty impressive and to the point. I really understand DP problems much better now. Similarly if we have a set of tree and graph interview questions it would be really be helpful thank you :)
Thanks a lot for the video. But I think to find the length of the longest substring we should not visit the matrix one more time, instead we can maintain an answer variable which will store the max value each time when we are updating the table. This will help to find the result in single pass.
Thanks for taking the time to explain, but one thing has confused me. Why place zero's in the columns that come after a value greater than zero? eg, col[3][4] 'abcd' and 'zbc', should hold 2, no? since at this point we have a sub-string of "bc"
I guess here the logic is- answer is not the cell value, but the answer is max value obtained until the cell value. So for the example you mentioned the answer is the max value found until the cells [3][2] which is 2.
@@bensmith1691 We cannot place 2 in a cell, because it may effect the subsequent results. But to find the length of max substring we need to find max from [0][0] to cell contain 'abcd' and 'zbc' which is cell [3][4]. Inshort the value of cell[3][4]=0 but the max length substring of cell[3][4] will be the max found from [0][0] to [3][4].
so it is always better to check previous questions for the interview. And this question is easily in the top 5 most asked easy coding interview questions.
He is not explaining it properly Watch Aditya Verma videos on Dp but they are not in English We should solve such questions recursively then memoise it OR solve recursively and convert it to top down approach Directly solving in top down approach is impossible
@@yadneshkhode3091 This a bottom up approach, we usually start with recursive top down approach, memoize stuff and end with an optimized bottom up solution.
At 2:25, he says since they are not same we put zero, put according to the explanation he gave earlier, it should have been "longest substring between zb and abc is zero" which would have been incorrect since it should be 1 (b is common) . Can anyone concur ?
Hi Tushar, I think what you are saying from 1:49 to 1:59 is wrong because....The values which we are putting in the matrix is "the Length of longest common suffix".....and not "Length of longest common substring". en.wikipedia.org/wiki/Longest_common_substring_problem#Dynamic_programming
Hi, Tushar, I have one question, while filling 4th row, when char 'c' comes into picture, common substring between "abc" and "zb", still we have length of common substring is 1, then why we are putting '0'. In short, if character doesn't match, then why we are putting zero, not the max(A[i-1][j] , A[i][j-1]). Please clear my concern.By the way , excellent video.
If we look at the matrix, the max value in such a case is still 1 which is the length of the longest common substring. What you are saying is applicable for longest common subsequence.
I think one thing you didn't explain clearly is that T[i][j] actually means the longest substring length ending with input[i] and input[j]. Note: that's different with longest substring length of s1.substr(0, i) and s2.substr(0, j). That's why the maximum result not necessarily the last T[0][N - 1].
if you take matrix cell mat[2][3]...it indicates longest common substring between abc and zb the longest common substring is 1 whereas you got 0 in the cell.You have missed the logic when the i and j are not same we need to consider exclude i or exclude j.
This isn't a mistake. The DP table isn't built in such a way that DP[i][j] gives you the longest common substring between string_one[1 ... i] and string_two [1 ... j]. Instead, to get the actual answer, you have to iterate over the table again.
@@adityakrishna11 Agreed, but during his initial explanation he clearly says that DP[i][j] gives you the longest common substring between string_one[1 ... i] and string_two [1 ... j]
To answer some questions, T[ i ][ j ] is the length of the common prefix between characters X1 ... Xi and Y1 ... Yj. So if T[ i ][ j ] = 3, then string(Xi-2, Xi-1, Xi) == string(Yj-2, Yj-1, Yj). He then looks through the matrix and returns the largest value (or keep track of the max value while running the algorithm and that is the longest common substring).
@2:24, "the longest common substring" between "abc" & "zb" should be "b", aka length 1. You put 0. This is throwing me off. Let's not call it the longest common substring within the matrix?
Hi Tushar Thank you for your video As for the code: you don't need to create the matrix Here is the code in python: # def longest_common_substr_(s,t): n=len(s) uprow=[0]*(n+1) index=-1 maxlen=0 for x in t: row=[0]*(n+1) for j in range(n): if x==s[j]: row[j+1]=uprow[j]+1 if row[j+1]>maxlen: maxlen=row[j+1] index=j uprow=row return s[index+1-maxlen:index+1] # def test(): s="abcdef" t="acbcf" print(s,t) substr=longest_common_substr_(s,t) print(substr)
there is a conflicting information. the matrix value represents the the LCS between 2 strings. e.g. "zb" and "abc". isn't that supposed to be 1 since 'b' is the common letter?
hey tushar can I know from where did u study dynamic programming (I mean source) also what is your educational background ( I mean where did u study and what did u study) all this is just out of curiosity after listening to all u r videos which were very nice
I understand from comments below that while checking zb and abc putting 0 at the intersection of b & c helps in the matrix because it helps you get to the accurate solution. But, what is it that drives you to choose 0 and not 1. Just saying that using zero helps get the solution seems like a trick one must know. If this is asked in an interview, I am afraid without knowing this specific trick, one will be unable to solve the problem. Can you provide a logical reason for putting 0 other than just because it gets the right answer.
Consider it this way, say we are comparing 'zb' and 'abc' , then we want to find the max length of the substring ending with b and c resp. (last character) , since it is not possible for string to have substring ending with b and c resp - hence we put 0 in that place. But for the case of say 'cbd' and 'abd', the last characters are both 'd's, so we do (1+the value in the left diagonal) - which should be 2.
Hi tushar, nice explanation but i have one doubt which is like we are talking about 3rd row and 4th column since we are trying for longest substring between (zb, abc) which is b of length 1 then why this is zero
+Priyanka Bajpai, a comparison check between the last characters of each string, in this case, b and c, is done. as B and C is not similar, you put a zero by default. Note that this is a common substring, not common subsequence! :)
Because if you think deeply about it, dp[i][j] gives us the longest common substring having first i characters in string 1 and first j characters of string 2 also common substring should be ending at S1[i-1] and S2[j-1]. That's why the answer is not dp[m][n] but the maximum in dp array in your example answer would be dp[1][1] but dp[2][3]=0 as the ending characters are not same.
Nice but what if you have two substrings that have same length. I mean let say your length longest substiring is 2 and you have AB DE will you return both of them ?
The actual recurrence relation for Construction of DP Matrix: LCS(i,j)=Max{LCS(i-1,j),LCS(i,j-1),x} calculate x: if(input[i]==input2[j]) T[i][j]=T[i-1][j-1]+1 else T[i][j]=0 For example: to caluculate LCS(2,3) i.eThe LCS(Longest common substring) between zb and abc since b != c x=0 , LCS[i][j-1]=1 & LCS[i-1][j]=0(from the table). so max is 1 among the 3.So cell value is 1 . Actually Tushar recursive approach in git link is correct while DP approach is wrong. Thanks.
can you please explain why do zero if input1[i] != input2[j] , consider the case when comparing string zbc to string abcd which is an entry in this table shouldnt the entry be 2 here we are having 0 , I am really confused please explain
+Tushar Roy , I agree with Ashwin's point. In the case when comparing string "zbc" to string "abcd", the longest common substring length should be 2 (as substring "bc" is contiguous in both the strings). Let me know if my understanding is not right.
Sir, if any letter is matched b/w two strings, while updating the max count , why we are adding only the upper diagonal index value, by adding that how u can say that the letters we r finding are adjacent in the string .
When you are comparing "ab" and "zbc" at that time answer should not be 1? Why you have put zero, as b and c are not same? But there is 'b' which is common in both. Can you explain me reason?
Great explanation!! While the DP explanation is awesome I think there is another solution to this problem in O(nlogn) (expected) time using rolling hashes and binary search. Though it may not be pertinent in this DP series i thought it might be helpful to know the alternatives!!
can anybody explain how this statement lcs.longestCommonSubstring works which will fetch Max from the method within main and display the Longest common string.. as the Max will contain the biggest integer at the end of program..
No it shouldn't. Think about it for a second or implement it. You will find the mistake in it. Remember that we are *finding* the longest common *substring* and *not subsequence*. The lengths will change if your take T[ i ][ j ] as T[ i-1 ][ j ]. Here is the reply from Tushar Roy which I found in one of the comments below *_If you followed video till the end you would see answer is not at bottom right corner. I iterate matrix again to find max number. Since its longest common substring we cannot store 1 at the point you said otherwise next comparison would think last 2 character were match and increment this by 1 if current 2 chars are match basically converting this into longest common subsequence._*
Oops..Here I made mistake...and the number in matrix is not representing representing length of common substring but it is common substring length from the ending index. So "zbc" and "ab" are not having end index common so it should be 0.
To find the longest common substring after constructing the matrix, you have to look for the biggest number, not the end of the matrix. Same to "zbc" and "ab". You should look at the matrix containing these two strings to get the answer.
***** Thanks :) By the way I found that, you have segment tree's code in your github. If possible can you please upload a video on SEGMENT trees? It will be really helpful if you can upload a video on segment tree. I have searched of similar videos on youtube. But the videos are not that helpful. I am sure you can explain it in the best manner. :)
yes, It's easier to solve w/o dp i.e. by taking each index as centre and expanding it in both direction but how do you come with O(n) solution. afaik this solution has O(n^2).
Sorry to say but your explanation has no mention about how this would not work for longest common subsequence. your solution , how does it account for the fact that it is a "substring" problem and not a "subsequence" problem ? Just drawing the table is not helpful...
oh my fucking god i hate coding but still somehow managed to cheat in microsoft online test and rest is history , i cracked that fucking interview and now i am working in microsoft at 39 a.pa
@Tushar: I would like to thank you for providing such a awesome information for larger community.
bhai kabhi milna unse to mere taraf se bhi bol dena
Those who are wondering why did we put '0' in those places where the characters didn't match, since in the longest common sub sequence we took the max of the two adjacent cells instead of putting '0'.
The biggest difference between longest common sub sequence and sub string is the way we interpret dp[i][j].
for Longest common sub sequence, dp[i][j] means the longest common sub sequence between "starting from 0 to i for string s1" and "starting from 0 to j in string s2",.
In contrast,
for Longest common sub string, dp[i][j] means the longest common sub string between S1 and S2 "starting from i and j"
This is very crucial to understand cause this is making all the difference. For sub sequence we are always starting from index 0 and finding out the longest value possible, for sub string we are always starting from the current index and iteratively increasing the value. Since for sub string they need to be consecutive that is why whenever we are finding there's a mismatch we are saying 0 cause starting from i, j so far we have not found any sub string.
hope this helps.
Thanks !
The guy cracks me up every time he says lets solve it by dynamic programming! Thank you for your videos
Your videos are pretty impressive and to the point. I really understand DP problems much better now. Similarly if we have a set of tree and graph interview questions it would be really be helpful thank you :)
Would be looking forward for it.. I must say great initiative.. :)
I think this is the easiest-to-understand video on YT about Longest Common Substring. Thanks!
Super video! You have explained this so beautifully that even algorithm challenged person like me understood it! Great work!
Another really great, straightforward and clear explanation. Wish you continued making videos.
It is great that you gave tabular explanation for all.Got an idea of what is happening during DP.......
Thanks a lot for the video. But I think to find the length of the longest substring we should not visit the matrix one more time, instead we can maintain an answer variable which will store the max value each time when we are updating the table. This will help to find the result in single pass.
The time complexity theoreticly wont change :)
Thanks for taking the time to explain, but one thing has confused me. Why place zero's in the columns that come after a value greater than zero? eg, col[3][4] 'abcd' and 'zbc', should hold 2, no? since at this point we have a sub-string of "bc"
I guess here the logic is- answer is not the cell value, but the answer is max value obtained until the cell value. So for the example you mentioned the answer is the max value found until the cells [3][2] which is 2.
@@rakeshreddy-et4yh OK so you are saying placing 2 could be correct, but depends on how we extract the final answer.
@@bensmith1691 We cannot place 2 in a cell, because it may effect the subsequent results. But to find the length of max substring we need to find max from [0][0] to cell contain 'abcd' and 'zbc' which is cell [3][4]. Inshort the value of cell[3][4]=0 but the max length substring of cell[3][4] will be the max found from [0][0] to [3][4].
Thanks for this comment, had the same doutbt.
how are you supposed to come up with this during a live coding interview? Like there's just no way unless you know the solution prior??
so it is always better to check previous questions for the interview. And this question is easily in the top 5 most asked easy coding interview questions.
He is not explaining it properly
Watch Aditya Verma videos on Dp but they are not in English
We should solve such questions recursively then memoise it OR solve recursively and convert it to top down approach
Directly solving in top down approach is impossible
@@yadneshkhode3091 This a bottom up approach, we usually start with recursive top down approach, memoize stuff and end with an optimized bottom up solution.
Yes i second that.
At 2:25, he says since they are not same we put zero, put according to the explanation he gave earlier, it should have been "longest substring between zb and abc is zero" which would have been incorrect since it should be 1 (b is common) . Can anyone concur ?
Hi Tushar, I think what you are saying from 1:49 to 1:59 is wrong because....The values which we are putting in the matrix is "the Length of longest common suffix".....and not "Length of longest common substring".
en.wikipedia.org/wiki/Longest_common_substring_problem#Dynamic_programming
Hi, Tushar,
I have one question, while filling 4th row, when char 'c' comes into picture, common substring between "abc" and "zb", still we have length of common substring is 1, then why we are putting '0'.
In short, if character doesn't match, then why we are putting zero, not the max(A[i-1][j] , A[i][j-1]). Please clear my concern.By the way , excellent video.
I have the same doubt.
If we look at the matrix, the max value in such a case is still 1 which is the length of the longest common substring. What you are saying is applicable for longest common subsequence.
I think tushar needs to answer this. I have same doubt
Yeah I also don't understand why we didn't put 1 there?
Hi Tushar, can you please help with this question?
thank u tushar for making dp so easy :)
I think one thing you didn't explain clearly is that T[i][j] actually means the longest substring length ending with input[i] and input[j]. Note: that's different with longest substring length of s1.substr(0, i) and s2.substr(0, j). That's why the maximum result not necessarily the last T[0][N - 1].
First video on youtube which has actually explained dp instead of providing mere formula.
Thank u sir
Now I am enjoying dynamic programming
if you take matrix cell mat[2][3]...it indicates longest common substring between abc and zb the longest common substring is 1 whereas you got 0 in the cell.You have missed the logic when the i and j are not same we need to consider exclude i or exclude j.
This isn't a mistake.
The DP table isn't built in such a way that DP[i][j] gives you the longest common substring between string_one[1 ... i] and string_two [1 ... j]. Instead, to get the actual answer, you have to iterate over the table again.
@@adityakrishna11 Agreed, but during his initial explanation he clearly says that DP[i][j] gives you the longest common substring between string_one[1 ... i] and string_two [1 ... j]
To answer some questions, T[ i ][ j ] is the length of the common prefix between characters X1 ... Xi and Y1 ... Yj. So if T[ i ][ j ] = 3, then string(Xi-2, Xi-1, Xi) == string(Yj-2, Yj-1, Yj). He then looks through the matrix and returns the largest value (or keep track of the max value while running the algorithm and that is the longest common substring).
Best explanation ever.
Dhanyavaad aur pranam
Thank you. Saved me a lot of time
so friendly! Thanks for the explanation!
@2:24, "the longest common substring" between "abc" & "zb" should be "b", aka length 1. You put 0. This is throwing me off. Let's not call it the longest common substring within the matrix?
💯 . I had the same question . The matrix he has filled is incorrect .
U are awesome. Explained this in so simple way...
Hi Tushar
Thank you for your video
As for the code: you don't need to create the matrix
Here is the code in python:
#
def longest_common_substr_(s,t):
n=len(s)
uprow=[0]*(n+1)
index=-1
maxlen=0
for x in t:
row=[0]*(n+1)
for j in range(n):
if x==s[j]:
row[j+1]=uprow[j]+1
if row[j+1]>maxlen:
maxlen=row[j+1]
index=j
uprow=row
return s[index+1-maxlen:index+1]
#
def test():
s="abcdef"
t="acbcf"
print(s,t)
substr=longest_common_substr_(s,t)
print(substr)
Your Videos are really very Helpful
there is a conflicting information. the matrix value represents the the LCS between 2 strings. e.g. "zb" and "abc". isn't that supposed to be 1 since 'b' is the common letter?
then, in that case, we can get the longest common subsequence
thanks mann, it was short and clear
Oh, I love your videos. Thanks!
You explain really well. Thanks
You sir are an absolute legend
Tushar bhai aap bhoot mast kaam karte ho...!
Tushar Roy is a God in dynammic programming!
hey tushar can I know from where did u study dynamic programming (I mean source) also what is your educational background ( I mean where did u study and what did u study) all this is just out of curiosity after listening to all u r videos which were very nice
I understand from comments below that while checking zb and abc putting 0 at the intersection of b & c helps in the matrix because it helps you get to the accurate solution. But, what is it that drives you to choose 0 and not 1. Just saying that using zero helps get the solution seems like a trick one must know. If this is asked in an interview, I am afraid without knowing this specific trick, one will be unable to solve the problem. Can you provide a logical reason for putting 0 other than just because it gets the right answer.
Consider it this way, say we are comparing 'zb' and 'abc' , then we want to find the max length of the substring ending with b and c resp. (last character) , since it is not possible for string to have substring ending with b and c resp - hence we put 0 in that place. But for the case of say 'cbd' and 'abd', the last characters are both 'd's, so we do (1+the value in the left diagonal) - which should be 2.
Great explanation. Would be even better if you explain the time & space complexity for each of the DP solution.
Why do we keep first row and first column as 0....I mean what's use case of that?
Excellent video! Great explanation.
very nice explanation.... if you are able to make a video on BSF and DSF please upload !! :)
Welcome ...n thank you so much
This is absolutely amazing
Hi tushar,
nice explanation but i have one doubt which is like we are talking about 3rd row and 4th column since we are trying for longest substring between (zb, abc) which is b of length 1 then why this is zero
+Priyanka Bajpai, a comparison check between the last characters of each string, in this case, b and c, is done. as B and C is not similar, you put a zero by default. Note that this is a common substring, not common subsequence! :)
@@swtdrmz58 But 'b' can be a common substring.
Why are you taking it as 0 if they are not same?
Like zb and abc
should have longest common substring cell as 1 no? You have done 0.
Why?
Because if you think deeply about it, dp[i][j] gives us the longest common substring having first i characters in string 1 and first j characters of string 2 also common substring should be ending at S1[i-1] and S2[j-1]. That's why the answer is not dp[m][n] but the maximum in dp array in your example answer would be dp[1][1] but dp[2][3]=0 as the ending characters are not same.
@@samiles171094 Kool , But Are you having some link where it is explained as such ... Coz Tushar doesn't mention this thing ??
He got wrong items in matrix . But no matter what u get answer correct if you put 0 or 1😊
Really amazing!!! Thank you for this video. Subscribed :)
Nice but what if you have two substrings that have same length. I mean let say your length longest substiring is 2 and you have AB DE will you return both of them ?
The actual recurrence relation for Construction of DP Matrix:
LCS(i,j)=Max{LCS(i-1,j),LCS(i,j-1),x}
calculate x:
if(input[i]==input2[j])
T[i][j]=T[i-1][j-1]+1
else
T[i][j]=0
For example:
to caluculate LCS(2,3) i.eThe LCS(Longest common substring) between zb and abc
since b != c
x=0 ,
LCS[i][j-1]=1 & LCS[i-1][j]=0(from the table).
so max is 1 among the 3.So cell value is 1 .
Actually Tushar recursive approach in git link is correct while DP approach is wrong.
Thanks.
OH MY GOSH YOU ARE SO AMAZING!!!! THANK YOU FOR THIS WONDERFUL TUTORIAL!!!!!!!!!!!!!!!!!!!!!!!
how do we get lexicographically first if there are more than one common substring of same length? @Tushar Roy
owsome explanation!!! plz make some video and explain how to identify DP questions!!
How would the logic change if it was substring in input1 and subsequence in input2?
Nicely done, thanks very much.
Thank you!! I got the approach. BUT
What is the intuition behind it (i.e using the idea of common suffix's)??
watch this to know the logic th-cam.com/video/ASoaQq66foQ/w-d-xo.html
sir what if i have single string separated by space and then i have to find longest common substring
can you please explain why do zero if input1[i] != input2[j] , consider the case when comparing string zbc to string abcd which is an entry in this table shouldnt the entry be 2 here we are having 0 , I am really confused please explain
+Tushar Roy , I agree with Ashwin's point. In the case when comparing string "zbc" to string "abcd", the longest common substring length should be 2 (as substring "bc" is contiguous in both the strings). Let me know if my understanding is not right.
Oh, it's easier than I thought, thx!
common don't say it is easy. keep that to yourself. it may be easy to you but not to others. what are you trying to say? you are a genius.!!!
What letter is the first one in the second string?
thanks for a great explanation .. got the whole picture by 2nd minute .. answers how and why DP is necessary
Great video... succinct and useful
why if the characters do not match it is dp[i][j] = 0 ? won't it be dp[i][j] = dp[i-1][j-1]
Sir,
if any letter is matched b/w two strings, while updating the max count , why we are adding only the upper diagonal index value, by adding that how u can say that the letters we r finding are adjacent in the string .
When you are comparing "ab" and "zbc" at that time answer should not be 1? Why you have put zero, as b and c are not same? But there is 'b' which is common in both. Can you explain me reason?
+Tushar Roy ahhh Got it. otherwise it will make next comparison value wrong. if we put 1 over there.
Thank you! Great explanation.
excellent solution..thanks man
Thank you Tushar, great explanation
Great explanation!! While the DP explanation is awesome I think there is another solution to this problem in O(nlogn) (expected) time using rolling hashes and binary search. Though it may not be pertinent in this DP series i thought it might be helpful to know the alternatives!!
clear and very easy explanation
Why do we put a 0 if the characters are not same?
+Kamal Chaya Because you want the longest COMMON substring. If the characters aren't similar then the common letters between them will be zero.
The only explanation I liked!
Awesome explanation man
I don't like how you use i and j, they both look too similar when written out.
Cant this problem be done without dp?
Dosent work for
"aacdefcaa" ??
can anybody explain how this statement lcs.longestCommonSubstring works which will fetch Max from the method within main and display the Longest common string.. as the Max will contain the biggest integer at the end of program..
between string "zbc" and "ab" the substring length should be 1 then why have you put it as 0 in the matrix?
I thought the exact same thing!! This algorithm isn't completely right.
Actually it is not affecting the answer but ideally it should be - if (input1 != input2) then T[ i ][ j ]=T[ i-1 ][ j ]
No it shouldn't. Think about it for a second or implement it. You will find the mistake in it. Remember that we are *finding* the longest common *substring* and *not subsequence*. The lengths will change if your take T[ i ][ j ] as T[ i-1 ][ j ].
Here is the reply from Tushar Roy which I found in one of the comments below
*_If you followed video till the end you would see answer is not at bottom right corner. I iterate matrix again to find max number. Since its longest common substring we cannot store 1 at the point you said otherwise next comparison would think last 2 character were match and increment this by 1 if current 2 chars are match basically converting this into longest common subsequence._*
Oops..Here I made mistake...and the number in matrix is not representing representing length of common substring but it is common substring length from the ending index. So "zbc" and "ab" are not having end index common so it should be 0.
To find the longest common substring after constructing the matrix, you have to look for the biggest number, not the end of the matrix. Same to "zbc" and "ab". You should look at the matrix containing these two strings to get the answer.
He is actually calculating longest common suffix in matrix not substring....He stated it wrongfully
Thanks a lot friend.. Very clear explanation...
why is the first column all zeros, what is the purpose of that
That is to avoid having to put extra 'if's that check if you're within the array bounds.
Why cant the same be applied to longest common subseq?
i would say subsequence solution is more logical and understadable than this....
"When you think something is difficult, an Indian guy will solve it for you" - said me 🤣
Thanks for the video Sir. Can we have a video posted on Topic- Longest Zig Zag Subsequence by using DP
Let’s say you have abcdaf and zb. Longest common sub string is 1 isn’t it? Why u are filling all indexes with 0 ??
Great explanation
Great explanation thanks.
Seriously "made simple" wooow!!! Tysm
great explanation
hey! can you please put up a video to to LCS using suffix array too? That would be really helpful :) By the way all the videos are simply the best! :)
***** Thanks :) By the way I found that, you have segment tree's code in your github. If possible can you please upload a video on SEGMENT trees? It will be really helpful if you can upload a video on segment tree. I have searched of similar videos on youtube. But the videos are not that helpful. I am sure you can explain it in the best manner. :)
OH! that is good news! Thanks bro :) all the best bro!
premium stuff! please add the video for Longest Palindromic Substring also using DP.
yes, It's easier to solve w/o dp i.e. by taking each index as centre and expanding it in both direction but how do you come with O(n) solution. afaik this solution has O(n^2).
that's kind of complexed, but thanks for the link.
Nice explanation !!
how can i find the expected value?
keep track of the indices of the highest value, then traverse diagonally
hmm, Tushar sir, your solution matrix is correct but the explanation is a little bit wrong.
The man, the myth the legend. Thanks Tushar!
Really Well explained!!!!
Sorry to say but your explanation has no mention about how this would not work for longest common subsequence.
your solution , how does it account for the fact that it is a "substring" problem and not a "subsequence" problem ?
Just drawing the table is not helpful...
Thanks man, you are awesome
great solution
oh my fucking god i hate coding but still somehow managed to cheat in microsoft online test and rest is history , i cracked that fucking interview and now i am working in microsoft at 39 a.pa
thanx a lot, this really helps
Osm explanation
Excellent 👌
awesome sir..