DP 27. Longest Common Substring | DP on Strings 🔥

[@gandhijainamgunvantkumar6783]

Amazing explanation brother. if anyone is confused about why we are taking dp[i][j] = 0, note that dp[i][j] here indicates the length of longest substring ending at index i of the s1 and index j of s2 string.

[@subasishkar9469]

I am not getting the mismatch condition only please can you elaborate

[@drj9403]

ha bhai thank you 😂

[@amansinghdalawat758]

right I needed to confirm with someone

[@jayantmishra2266]

Small Correction : note that dp[i][j] here indicates the length of longest substring ending at index i-1 of the s1 and index j-1 of s2 string, cause here i and j refers to length of s1 and s2 respectively, so access last char of s1 and s2 we'll do s1[i-1] and s2[j-1].

[@SohailKhan-cx9gb]

​@@jayantmishra2266yes bro because in tabulation we cannot write the negative condition so we have shifted i-1 to i

[@PIYUSHRAJ-t5v]

Just pointed out We can ignore the base case and else condition . it still works as the dp array is initially filled with with zero only. So no need to again assign 0 to it.

[@tawhidjoarder756]

This guy really deserves a medal.

[@chandanbera2692]

Recursion solution static int lcs(int m, int n, String s1, String s2, int count) { if(m

[@parthsalat]

Dev manus 🙏

[@ankitparashar8730]

By memorization it takes cubic time complexity

[@hemanthreddysodum-x4w]

i did the same thing but i am getting WA after converting this recursive code to memo code whyy??

[@StudyMan-pf9tn]

@@hemanthreddysodum-x4w no overlapping sub problems

[@shaileshsingh6771]

We can space optimize it to 1D array:- int findLength(vector& nums1, vector& nums2) { int n = nums1.size(), m = nums2.size(); int maxLength = 0; vector prev(m+1,0); for(int i=1; i0; j--) { if(nums1[i-1] == nums2[j-1]) { prev[j] = 1 + prev[j-1]; maxLength = max(maxLength,prev[j]); } else prev[j] = 0; } } return maxLength; }

[@sanginigupta1312]

Here, arr[i][j] can mean the longest substring that ends at ith character in string 1 and at jth character in string 2, and we take the max of all the combinations!

[@rossgeller9372]

if anyone wants a recursive approach for this, here it is-> src: int lcsHelper(string &str1, string &str2, int n, int m, int count){ if (m == -1 || n == -1){ return count; } if (str1[n] == str2[m]){ count = lcsHelper(str1, str2, n - 1, m - 1, count + 1); } count = max({count, lcsHelper(str1, str2, n - 1, m, 0), lcsHelper(str1, str2, n, m - 1, 0)}); return count; } int lcs(string &str1, string &str2){ return lcsHelper(str1, str2, str1.length() - 1, str2.length() - 1, 0); }

[@ravindrayadav6103]

why this memoization code gives wrng ans-//{ Driver Code Starts #include using namespace std; // } Driver Code Ends class Solution{ public: int dp[1001][1001]; int solve(string S1,string S2,int n,int m,int cnt){ if(n==-1||m==-1)return cnt; if(dp[n][m]!=-1)return dp[n][m]; if(S1[n]==S2[m]){ cnt= solve(S1,S2,n-1,m-1,cnt+1);} else{ cnt= max({cnt,solve(S1,S2,n-1,m,0),solve(S1,S2,n,m-1,0)}); } return dp[n][m]=cnt; } int longestCommonSubstr (string S1, string S2, int n, int m) { memset(dp,-1,sizeof(dp)); int cnt=0; return solve(S1,S2,n-1,m-1,0); } }; //{ Driver Code Starts. int main() { int t; cin >> t; while (t--) { int n, m; cin >> n >> m; string s1, s2; cin >> s1 >> s2; Solution ob; cout

[@SorcererSupreme73]

mr geller i thought you were a paleontologist

[@justice5777]

@@SorcererSupreme73 yeah i also thought he's a polontologist

[@naamhaii]

memoization is not work on this

[@naamhaii]

@@ravindrayadav6103 not working on these TC 1)yxyy yxy ans->3 2)yxxzzxxxx yzyzxxyxxz ans->4

[@himanshuagrawal8012]

#UNDERSTOOD Bhaiya...I am now able to develop logic before watching the video...still I watch video after submitting just to go through once and to see your energy level...🙂🙂😍😍

[@stith_pragya]

UNDERSTOOD.........Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@divyendragahlot9231]

You should have told the recursive approach too. You had done that in all the previous videos.

[@vikasbelida3218]

here's the recursive solution: public int lcs(int[] A, int[] B, int m, int n, int res) { if (m == -1 || n == -1) { return res; } if (A[m] == B[n]) { res = lcs(A, B, m - 1, n - 1, res + 1); } return max(res, max(lcs(A, B, m, n - 1, 0), lcs(A, B, m - 1, n, 0))); }

[@rishabhgupta9846]

@@vikasbelida3218 can you share memoization one also ,I'm not able to do it

[@ravianand3498]

@@allideas777 res is also changing so that also needs to be considered in dp table,so there are 3 parameters therefore 3D array is needed.

[@datahacker1405]

Only real programmers can do that because you won't find recursive approach at most of the places. Most of these youtubers understand the omnipresent solution and explain it here with a few additions here and there.

[@av21015]

@@datahacker1405 is it even possible to solve this using memoization? I tried but couldn't

[@munnakrish3572]

understood!..Thanks for explaining this in an elegant way!

[@raghavmanish24]

this question like one of the easiest question after following your videos....thanku striver

[@LORDGULSHAN]

Striver, Please make a video on how to print Longest Palindromic Substring, because reversing the string technique won't work like we did for Longest Palindromic Subsequence.

[@papayasprout]

Why will it not work?

[@lokeshdohare2579]

@@papayasprout Because this approach will fails when there exists a reversed copy of a non-palindromic substring in some other part of our original string. Ex - "aacdacaa"

[@omkumarsingh4194]

@@lokeshdohare2579 i am facing the same problem, did u come up with any modification over striver's code

[@lokeshdohare4872]

@@omkumarsingh4194 I came up with a solution, but that's not a dp solution.

[@omkumarsingh4194]

@@lokeshdohare4872 alright, can u share that. Btw I solved using same dp by striver . Just introduced one condition when u are updating ans that is I-dp[I][j] == n-j. Means we are checking whether startpoint of both substrings is same

[@googleit2490]

Done and dusted in the revision session :) Nov'14, 2023 04:37 pm

[@dadidivya8663]

Just in case if anyone needs recursive approach for this: Recursive code: def lcs(s, t) : def solve(i1,i2): if(i1

[@ScrollWthMahadev]

best

[@KunalJaiswal-og7nf]

@@ScrollWthMahadev can convert to c++??

[@sharmaanuj334]

Hey, I am not able to understand why you have done nomatch = min(solve(), solve(), 0) since it would always give 0 for nomatch

[@tejaswi4650]

same question@@sharmaanuj334

[@harshitsen5479]

In the no-matching condition in the case of subsequence we were basically skipping one element from the str1 in the first recursion call and one element from the str2 in the second recursion call (since subsequence can be or cannot be continous), but in the case of substring we cannot skip an element to form a substring (as it must be continous). So that's why we returned 0 straight away.

[@nitin50056]

Can you share a memoization solution ?

[@vinaykumar9002]

Equivalent leetcode question for this is "718. Maximum Length of Repeated Subarray "

[@itslol6504]

Thanks !

[@AquaRegia-i3u]

Thanks man. Appreciated.

[@rohitanjane1668]

Thanks bro...👍🏻

[@tasneemayham974]

UNDERSTOOOD UNDERSTOOOD UNDERSTOOOD!!! BEST TEACHERRRR EVERRRRR!!!!!!!!💯💯💯💯

[@vikasbelida3218]

incase anyone looking for recursive solution: public int lcs(int[] A, int[] B, int m, int n, int res) { if (m == -1 || n == -1) { return res; } if (A[m] == B[n]) { res = lcs(A, B, m - 1, n - 1, res + 1); } return max(res, max(lcs(A, B, m, n - 1, 0), lcs(A, B, m - 1, n, 0))); }

[@sonalidutta825]

here's an easy to understand recursuve solution without using any for loop. core logic: 1. since it's a substring we will be doing m-1 and n-1 call only when s1[n]==s2[m] in the next call thats why checking => if(n > 0 && m > 0 && s1[n-1]==s2[m-1]). 2. now suppose in current recursion s1[n]==s2[m] and i'm doing this: take = 1 ; if(n > 0 && m > 0 && s1[n-1]==s2[m-1]) take += nxt_recusrion; so whatever is the value of nxt_recusrion it should be returned by the take part only eg: s1 = abcde, s2 = abfde 1st rec: take1 = 1 (for [e]) + nxt_recursion(for [d]) notTake1 = max(nxt_recursion(for n,m-1), nxt_recursion(for n-1,m)) 2nd recursion: s1=abcd, s2 = abfd take2=1 i.e. [d] in take1, nxt_recursion(for [d]) should be equal to take2. notTake1 should be equal to max(take2, notTake2) we can conclude for take part answer should be returned from next recursion's take part only. to achieve this i have used: if(n

[@ShubhamVerma-hw4uj]

for those who want to solve this question on leetcode, it is lc 718

[@codecrafts5263]

thanks!

[@parthib_deb23]

make a well-built hashmap and check within it. Its possible to do in O(N) time. There is a simple reason behind it - In subsequence the order of words doesnot matter which makes the solution prone to more edgecases but in substring , even if there is one single character unmatched you can't go forward

[@user-of5qt4yn5j]

understood striver,may god bless you

[@thanushreddy1020]

Understood !! Thank You, for your hard work..

[@aakashbhandari9761]

Sir understood Well! , But just want to ask is the below code is right ? String a="aakabdqwer"; String b="abkasxgdqwer"; int i=a.length()-1; int j=b.length()-1; int count=0; int ans=0; while(i>= 0 && j>= 0){ if(a.charAt(i)==b.charAt(j)){ count ++; i--; j--; }else{ count=0; i--; j--; } ans=Math.max(count,ans); } System.out.println(ans);

[@wrongnotes1157]

here is the memorization method: int lcsUtil(string& s1, string& s2, int n, int m, vector& dp) { if (n == 0 || m == 0) { return 0; } if (dp[n][m] != -1) { return dp[n][m]; } int result = 0; if (s1[n-1] == s2[m-1]) { result = 1 + lcsUtil(s1, s2, n-1, m-1, dp); } else { result = 0; } dp[n][m] = result; return result; } int lcs(string& s1, string& s2) { int n = s1.size(); int m = s2.size(); vector dp(n+1, vector(m+1, -1)); int ans = 0; for (int i = 1; i

[@anshumaan1024]

nice brother this is working

[@ishanporwal4403]

how is it different from the brute force as this also has TC O(n^3) ans the TC of brute force id also O(n^3)

[@SohailKhan-cx9gb]

Same bro 🤜

[@Himani-t3g]

understood! striver

[@shuvbhowmickbestin]

is there a reason why we're not talking about the memoization approach here? I kinda know the answer but it'd be better if the memoization approach is also discussed or told why it is not being considered for this problem because we always go from recursion to memoization to tabulation. This is the right approach for solving DP problems.

[@DevashishJose]

Understood, Thank you so much.

[@ritikshandilya7075]

Thanks for great solution Striver

[@madhukartemba2987]

Striver sir, this problem can also be solved by using just one array by traversing from the back: import java.util.*; public class Solution { public static int lcs(String str1, String str2) { int n1 = str1.length(); int n2 = str2.length(); int prev[] = new int[n2+1]; int ans = 0; for(int i=1; i0; j--) { if(str1.charAt(i-1)==str2.charAt(j-1)) { prev[j] = 1 + prev[j-1]; } else { prev[j] = 0; } ans = Math.max(ans, prev[j]); } } return ans; } }

[@harshjain8823]

How its working ? what is the intuition ..

[@ayonsinha2075]

@@harshjain8823 it's just 1d conversion of 2 individual 1d ..and for curr in matching condition curr[index2]= prev[index2-1]...so u just nedd prev[index2-1] so...u can rewrite on prev array itself from n2 to 0 because for current index u only need value of just previous index..so u can easily rewrite it..

[@gsampath8017]

from where have you learned dsa ?? if you have not understood a specific topic how to handle it??

[@alexrcrew1975]

search is the only solution go n search

[@CryptoZombie666]

UNDERSTOOD, Striver Bhaiya! Here's Another Brute force method WITHOUT USING DP: int lcs(string &str1, string &str2){ int n = str1.size(), m = str2.size(), maxLen = 0; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(str1[i] == str2[j]){ int ptr1 = i, ptr2 = j; int currLen = 0; while(ptr1 < n && ptr2 < m && str1[ptr1] == str2[ptr2]){ currLen++; ptr1++, ptr2++; } maxLen = max(maxLen, currLen); } } } return maxLen; }

[@Hrushi_2000]

Understood. Thankyou Sir

[@ranasauravsingh]

UNDERSTOOD...!! Thank you striver for the video... :)

[@FunkyPanda6263]

1-Array space optimised solution. int lcs(string &s1, string &s2){ int len1 = s1.length(), len2 = s2.length(); vector state(len2+1); int prev = 0; int temp, res = 0; for(int i=1; i

[@koocheukkeijacky9704]

amazing teacher.

[@rohandas6298]

Single 1D Array space optimization: int lcs(string &s, string &t){ int n=s.size(),m=t.size(); vector cur(m+1,0); int maxi=0; for(int i=1;i

[@souvikbiswas284]

Dropping Single Row Optimization for anyone in need: m, n = len(text1), len(text2) prev = curr = [0]*(n+1) max_len = 0 for i in range(1, m+1): prev_j_min_1 = prev[0] for j in range(1, n+1): ans = prev_j_min_1 + 1 if text1[i-1] == text2[j-1] else 0 prev_j_min_1 = prev[j] curr[j] = ans max_len = max(max_len, curr[j]) return max_len

[@ntgrn-pr5yx]

thank you US

[@aruna5869]

understood :)❤ still we can optimise this to one array by a loop m to 1

[@yugal8627]

I got the intuition within 4mins of you video.😎😎

[@explainedmathmaticsranjeet1404]

can we further optimize in 1 d araay?

[@dhairyachauhan6622]

using recursion c++ #include int solve(int n, int m, string &s1, string &s2, int count){ if(n == 0 || m == 0){ return count; } if(s1[n-1]==s2[m-1]){ count = solve(n-1, m-1, s1, s2, count+1); } int count2 = solve(n, m-1, s1, s2, 0); int count3 = solve(n-1, m, s1, s2, 0); return max(count, max(count2, count3)); } int lcs(string &str1, string &str2){ return solve(str1.length(), str2.length(), str1, str2, 0); }

[@ITACHIUCHIHA-dr8sz]

what about memoization ?

[@tejasghone5118]

Can also be done in O(1) space if we just traverse along the diagonals and keep max consecutive match count

[@takeUforward]

Nah nah, you need the previous values as well.. as in case its not matching. You need to know max!

[@tejasghone5118]

@@takeUforward int ans=0; // diagonals starting from first row for(int i=0;i

[@sparshyadav9709]

Understood.

[@nimeshsingh6229]

I think this can not be solved by memoization ie: top-down won't work here ?? please reply

[@anshumaan1024]

I have searched the whole comment section, i couldn't find any memoized code which has passed all test cases ig you are right

[@KCODivyanshuKatyan]

The energy man 🙌🔥

[@santoshb7776]

Understood sir !

[@maradanikhil6882]

here is the recursive & memoization approach.......... // recursive int func(int ind1,int ind2,string &s1,string &s2,int &ans){ if(ind1

[@anshumaan1024]

Bhai aapka memoization ka code toh pura recursive hai, joh aapne dp[][] array pass krri hai uska kuch use hi nhi hai recursive code shi lga 🙂

[@maradanikhil6882]

@@anshumaan1024 you are correct bro, return dp[ind1][ind2]=match ; now,it will be working fine ,thanks

[@kushalgupta2041]

@@maradanikhil6882 na bro it will give you wrong answer try it and even if you want to do it recursive way the time complexity will be like brute force

[@ll-ex5mh]

Memoization solution with 2d dp C++=> class Solution { public: int memo(int i,int j,vector&dp,vector& nums1, vector& nums2,int &maxlen) { if(i

[@UECAshutoshKumar]

Thank You Understood!!!

[@sumitgupta310]

understood striver

[@vidyasagarrvsr3723]

Hey ,i have a doubt according to this code logic, dp[2][2] will get 2 rightt?how zero??? since str1[1]==str2[1] and there is condition to check str1[i]==str2[j]

[@dheerajolakkal4268]

How are ppl coming with such simple solutions

[@priyagrajsharma9390]

Which board ?? Approach explanation k liye Jo board ya application use ki h konsi h ?

[@muchmunchies43]

Understood!

[@mohitsingh13]

Understood ❤🔥🔥

[@tusharsahu907]

understood …excellent series

[@dheerajshukla7008]

understood sir

[@zhunzargulhane6741]

In space optimization why do we take the length of prev and curr as length of str2.length()+1 why not str1.length()+1.

[@uday_berad]

// memoization in C++ class Solution { vector dp; public: int rec(int i,int j,vector& nums1, vector& nums2,int &ans){ if(i

[@rahultiwari7714]

understood bhayiya as always thank u for all

[@jyothiyadav2595]

Understood ❤❤❤❤

[@samarthsinghthakur]

If someone can clear my doubt. Can someone tell me what does dp[ i ][ j ] means? --- dp[ 1 ][ 2 ] is 0 What does dp[ 1 ][ 2 ] means here? What the longest common substring where i = 1 and j = 2; ie str1 = "a" and str2 = "ab" I am certain that's not the meaning here since dp[ 1 ][ 2 ] is 0 . ---

[@State_exam_preparation]

Dp[1][2] means a from str1 and b from str2. So a and b is not substring so O

[@baka_kuldeep]

Here is the code for Space Optimization to 1 1D array- int lcs(string &str1, string &str2){ int n = str1.length(); int m = str2.length(); int ans = 0; vector dp(m+1,0); for(int i=1;i=1;j--){ if(str1[i-1]==str2[j-1]){ dp[j]= 1+dp[j-1]; ans=max(ans,dp[j]); } else dp[j] =0; } } return ans; }

[@KushagraJarwal]

Can you explain how this is showing correct results even when we are checking the wrong string indexes like I=1 and j=m in the first iteration

[@verma_jay]

understood

[@siddharthjain4251]

please add the recursive approch here for lcs

[@takeUforward]

Its complex, and is of higher tc, so not required.

[@anshumaan1024]

class Solution{ public: int f(int i, int j, string &s1, string &s2, int &ans){ if( i

[@sufiyan0211]

Amazing observation!

[@dipaligangawane980]

Very good explanation. Thank you so much.

[@sanjitvyas3043]

Understood

[@kumarpurushottam632]

Understood Thanks 😀

[@rlm3227]

I used to think, this is a. good hard problem, but turns out this is just a 1000 rated problem on CF

[@NARUTOUZUMAKI-bk4nx]

UNDERSTOOD

[@InbasekaranP]

Hey striver, this method of finding the longest common substring fails when there exists a reversed copy of a non-palindromic substring in some other part of S. S = “abacdfgdcaba”, S’ = “abacdgfdcaba”. The longest common substring between S and S’ is “abacd”. This is not a valid palindrome. As there is a reverse copy of "abcd" ie "dcaba" which is non-palindromic substring in some other part of S, the longest common substring method fails. To fix this we just need to check if the substring’s indices are the same as the reversed substring’s original indices. If it is, then we attempt to update the longest palindrome found so far; if not, we skip this and find the next candidate. Here is the modified code for the above question: ```cpp class Solution { public: string longestPalindrome(string a) { int n = a.length(); string b = {a.rbegin(),a.rend()}; pair ans = {INT_MIN,{-1,-1}}; vector dp(n+1,vector(n+1,0)); for(int i = 1;i

[@hardikjain6397]

Thanks bro. It helped

[@mohitsoni2919]

For striver code as well we are getting lcs as 5 bro

[@sushant8686]

brute force will take same time na ?

[@hashcodez757]

Understood Bhaiya!! Edit after 4 months - "UNDERSTOOD BHAIYA!!"

[@ratinderpalsingh5909]

Understood, sir. Thank you very much.

[@_ShouravChy]

Printing the LCS: #include using namespace std; int main() { string s1,s2; cin>>s1>>s2; int n= s1.size(); int m = s2.size(); vectordp(n+1,vector(m,0)); int res = 0; int startIdx = -1, endIdx = -1; int st = INT_MAX; for(int i=1;i

[@SohailKhan-cx9gb]

Understood bro but the memoization and recursion is quite tough in recursion there is 3d have made😅

[@stain0p101]

Understood !!

[@parthib_deb23]

class Solution: def findLength(self, nums1: list[str], nums2: list[str]) -> int: if nums1==nums2: print(len(nums1)) elif nums1==[] or nums2==[]: print(0) elif nums1==nums2[::-1]: count=1 for i in range(1,len(nums1)): if nums1[i]==nums1[i-1]: count+=1 return count else: map={nums1[i]:set() for i in range(len(nums1))} map[nums1[0]].add(nums1[0]) for i in range(1,len(nums1)): map[nums1[i]].add(nums1[i-1]) print(map) temp_iter=[] temp=0 final=[] count=0 for i in range(len(nums2)): if nums2[i] in map.keys(): if temp==0: temp=1 else: if nums2[i-1] in map[nums1[i]]: if nums2[i-1] not in temp_iter: temp_iter.append(nums2[i-1]) temp_iter.append(nums2[i]) temp+=1 else: if temp>count: final=temp_iter count=temp temp=0 temp_iter=[] return count print(Solution().findLength(['1','2','3','2','1'],['3','2','1','4','7'])) print(Solution().findLength(['0','0',1],['1','0','0'])) this is the approach

[@joshua_dlima]

lovely explanation, thanks!

[@kushalsingh7789]

thanks man

[@m-bk4um]

understand

[@shubhamsalunkhe137]

Understood

[@subasishkar9469]

Hi @striver I am not getting the mismatch condition why we are using 0 in this case and have been stuck at it for quite some days now please can you explain , really stuck at this condition

[@shivamnagar9368]

Hey Striver, i m getting wrong ans in java code in space optimization, same happened with lcs space optimization

[@arpnasjs9825]

#UNDERSTOOD!

[@coder4]

Bhaiya what is the next topic in ur Dsa series? After DP

[@dipanshugupta6995]

thanks a lot sir for the playlist

[@udaypratapsingh8923]

done with it ! moving to next

[@sauravchandra10]

Understood, thanks!

[@raj_kundalia]

Thanks for the video!

[@iamnoob7593]

US striver

[@adebisisheriff159]

Understood!!!!

[@gangsta_coder_12]

UNDERSTOOD💯💯💯

[@vattiyeshwanth282]

so here dp[i][j] indicates that longest common substring in which s1[i] and s2[j] are matching?

[@codenchill732]

Consistency 🔥