Longest Common Substring Dynamic Programming

Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. Here you will learn about the Longest Common Substring . In this question :
1. You are given two strings S1 and S2.
2. You are required to print the length of the longest common substring of two strings.
For a better experience and more exercises, VISIT: www.pepcoding....
Have a look at our result: www.pepcoding....
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education

[@VKBMath]

This type of content is free unbelievable Love you Sumeet sir what a teacher ❤️❤️❤️❤️❤️❤️

[@Pepcoding]

wow, this cheers me up. I am glad we at pepcoding could be of help to you. Keep learning. Also, recommend us to your juniors and peers, they may also benefit.

[@prateeksharma3698]

No one gave this kind of insight of the problem , the WHY portion explained is excellent. Thanks Sir for such a great content.

[@simakeshri5890]

Aaj real meaning smj m aaya,baki log to bus dp bharna batate h. 👍👍. Thank you sir for these free content

[@sadmanabedin1203]

I solved this problem without even watching this video, using the techniques brother Sumeet taught in earlier problems like Longest palindroming substring, longest common subsequence etc. That proves how extremely good he is at teaching these staffs. Keep it up bro.

[@kartikshrivastava1500]

When asked how some tabulation solution works very few people know what's happening inside it, you are the one who knows inside-out of it, thanks a lot for sharing!

[@samarthjain5295]

This video deserves a like tbh, I have seen so many videos on this question but this is the only video saying that why it is happening .Thank you

[@shashwatagarwal867]

This is by far the most amazing explanation to this problem. Hats off!

[@Ali-ok8yn]

Best explanation for this question on the internet. DP solutions are always easy but the important part is how you reached that solution and you have explained that really well.

[@abhinavagrawal6148]

The way he explains agar koi interview me explain kre to interviewer wahi fan ho jaye.

[@sameersondur9030]

There are only 2 words that come to my mind!! ekdum jhakaas!!!! I had seen 3 videos till now for this problem and this is the first video I understood.

[@a026devpatelsvnit7]

This is the most underrated channel for programming on youtube

[@basudebshyam7840]

Why u did? J

[@sahilanower9189]

This channel is a life saver

[@rishabhkumar8115]

i really impressed by your explanation. thanks man for this.

[@Pepcoding]

Thankyou beta! I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem. If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )

[@helloword3544]

This question can be done in other way also , i.e, we can also evaluate longest common substring by comparing all suffixes of s1 with all suffixes of s2 and find the longest common prefix .

[@Pepcoding]

yes, true.

[@mickyman753]

can you share your code

[@abhisheksamari4591]

Excellent explaination

[@imajt5]

Dil se thank you bhai for providing the best content and giving so much time and effort to help us.

[@Pepcoding]

Thankyou beta! I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem. If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )

[@TheDev05]

All time GOAT, Summet Sir! 🙏

[@shivammehta9661]

Awesome Explanation......Keep making videos

[@democrats9579]

Woah❤ isse kehte h explaination🙌, this was amazing!

[@shivcharansinghrawat4224]

THE BEST EXPLANATION !!!!!!

[@Pepcoding]

Thank you! Cheers! For better experience and precisely arranged content visit on nados.pepcoding.com Don't forget to follow us on Instagram instagram.com/pepcoding/

[@rakshaverma3673]

you are really too good sir.......

[@vivekgupta_3085]

Good Content as usual .

[@gaunikasrivastava7851]

This explanation really gave a feel of the solution. Even better than AV's video

[@Pepcoding]

Glad, it was helpful For better experience and well organised content sign up on nados.io

[@AnandKumar-kz3ls]

we can use unordered_set and time complexity can reduced to n^3

[@akshayjadhav4199]

super explained 💥💥💥💥💥💥💥💥

[@akshatgupta2607]

One of the best explanation ❤️

[@varsha4260]

Sir,Please make a video on a backtracking solution of longest comon substring.

[@stutij7922]

Extremely well explanation sir

[@yashgoyal6079]

Wonderful explanation sir🙏🙏🙏🙏

[@aemenlodhi]

Great explanation. Thank you!

[@indranilchakraborty5949]

nice explanation sir...... akdm clear ho gya.😊😊😊😊

[@Pepcoding]

Bhot he bdiya, aise he lge rho aur bdte rho😊🙏

[@aman6561]

Sr bina trick jaane ke sbhi prefix ka common suffix ans hai to kaafi mushkil hai complexity km krna. agr trick pta ho tbhi hoga km complexity me

[@cplearners9244]

Sir, please make a video on finding common substring of n strings.

[@pranjalsharma499]

Sir you are doing a very good job, keep going

[@Pepcoding]

Thank you, I will

[@simrankak7045]

sir your explaination is so very good thankyou :)

[@sarveshmishra8416]

Wonderful explanation !!

[@RohitKumar-po5qt]

Brilliant brilliant brilliant !!!!

[@lochannatesh6684]

MInd blowing explanation...super

[@Pepcoding]

Thank you so much 🙂 and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )

[@AnkitSingh-xp7mm]

I was wondering, brute force complexity should be : O(n^2 + m^2 + n.m). O(n^2) for prefix of first string. O(m^2) for prefix of second string. Then Each element of first prefix list gets compared with second prefix list. Hence O(n.m) Total Complexity: O(n^2 + m^2 + n.m). Please correct me if I am wrong.

[@mickyman753]

n^2 susbtring will be made of first list ,m^2 in another , we will compare everyone of them so n^2*m^2 and each string comapision will take k(max len of both) time , so n^2*m^2*k

[@cracko3483]

Great Explanation Sir

[@Pepcoding]

Thankyou beta If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )

[@cracko3483]

@@Pepcoding Done Sir

[@harshvardhansingh780]

Great explanation sir

[@Pepcoding]

Glad you liked it! Keep learning And for better experience, visit nados.io, where you will get well curated content and career opportunities.

[@parthmadan671]

Awesome

[@MGtvMusic]

Some space optimisation : class Solution{ int longestCommonSubstr(String S1, String S2, int n, int m){ // code here int[] prev = new int[S2.length()+1]; int max = 0; for(int i=1;i

[@vaibhavjha5938]

👍. Sir can you plzz guide me regarding scope of placement after doing MTECH from IITB.I mean to say if I do good there will I get good tech companies.

[@amandixit3555]

ok , whosoever understood this question try thinking out can we do like we are going to store in each cell i , j the LCS between s1(0,i) and s2(0,j). If you figured out the way doing so ,good and if not , why not . comment down below. This will make the understanding of this question crystal clear in your mind. #HAPPYCODING.

[@stevejob677]

thank you so much sir

[@ashwinnema06]

This is the first question of tabular dp I solved without watching the solution

[@sarveshchavan4391]

Nice explain ❤️❤️

[@aman6561]

sir leetcode pr problem krra tha hashmap tag ki to usme ye question bhi tha bs array die the string ki jgh mne to dp lgaa kr submit krdia lekin solution me hashmap se bhi solution tha kch ROLLING HASH krke kya hota hai sr ye?.

[@tanishkumar6682]

understood

[@manishkumarsingh4631]

38/79 done

[@MGtvMusic]

Love you

[@madhavchaturvedi4654]

sir ji ye vala question memoization se kardo plz.Iska recursive formula banana bohot mushkil pad raha hai

[@RitikKumar-bk6pj]

Sir please tell how we will get the longest common string not their length?

[@RitikKumar-bk6pj]

@@Kashish_Batra thank u so much

[@SudhanshuKumar-jl8iw]

I like your explaination ways what?how ?why?it make me think a problem of dp easy ???

[@Pepcoding]

Thankyou beta, I am glad you liked it. I also hope that you are watching till end. If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )

[@priyanshugupta8299]

Can't we just solve it like longest common subsequence and simply store 0 whenever characters are unequal

[@Pepcoding]

For better insight, visit nados.pepcoding.com, post your doubts, community will help you out there.

[@rahulborule8619]

Can anyone guide me if I want to print that substring itself as output then how should I proceed

[@mickyman753]

you can take out the length of substring first and store the i and j index of that column , s.susbtring(i-lcs,i) [this is java substring method] will be our answer

[@randomname2444]

Sir, Can you upload egg drop problem tomorrow?

[@Pepcoding]

aj nahi kal

[@schwarzenneger9240]

sir 8 easy questions aane the na dp se pehle ?

[@subhamthakur565]

bhai aane de jo video daal rhe h saahi h SIR kuch soch ke hi daal rhe honge

[@schwarzenneger9240]

@@subhamthakur565 yar sir ne khud hi kaha hai ki pehle 8 easy fir 2 dp isliye pucha

[@shubhamaggarwal8957]

brute complexity will be n(n2 +m2) no n. n2 .m2