1. WRONG!
The else part is wrong in recurrence. When i!=j it will be max of i-1,j and i,j-1

2. I don't like how you use i and j, they both look too similar when written out.

3. Awesome explanation man

4. thanx a lot, this really helps

5. Note to myself: 2:00

6. Tushar Roy is a God in dynammic programming!

7. this is awesome!

8. Osm explanation

9. Super video! You have explained this so beautifully that even algorithm challenged person like me understood it! Great work!

10. Great video… succinct and useful

11. hmm, Tushar sir, your solution matrix is correct but the explanation is a little bit wrong.

12. Why cant the same be applied to longest common subseq?

13. for strings, ZBCDZ and ZFBCD answer should be 3 but I will get 1 if I go through this approach.

14. Thank u sir
Now I am enjoying dynamic programming

15. Marco Cusicanqui León

Excellent 👌

17. SANCHIT BATRA 16BEC1292

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?

18. The only explanation I liked!

19. 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.

20. if you take matrix cell mat…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.

21. 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 'abcd' and 'zbc', should hold 2, no? since at this point we have a sub-string of "bc"

22. Cant this problem be done without dp?

23. Thanks a lot friend.. Very clear explanation…

24. The man, the myth the legend. Thanks Tushar!

25. Awesome..thanks man 🙂

26. Thanks for the video Sir. Can we have a video posted on Topic- Longest Zig Zag Subsequence by using DP

27. Hi Tushar
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=*(n+1)
index=-1
maxlen=0
for x in t:
row=*(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)

28. Nicely done, thanks very much.

29. 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

30. 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?

31. thanks Tushar.

32. Seriously "made simple" wooow!!! Tysm

33. wow great

34. why is the first column all zeros, what is the purpose of that

35. Oh, it's easier than I thought, thx!

36. Thanks A lot

37. How would the logic change if it was substring in input1 and subsequence in input2?

38. thanks for explain bro

39. good video!!

40. sai karthik cheedella

how do we get lexicographically first if there are more than one common substring of same length? @Tushar Roy

41. 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.