DP 27. Longest Common Substring | DP on Strings 🔥 

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.

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

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.

This guy really deserves a medal.

#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...🙂🙂😍😍

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

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; }

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); }

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!

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

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

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

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

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

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

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.

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.

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

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

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

Can you share a memoization solution ?

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.

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);

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))); }

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; } }

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

Understood ❤

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

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); }

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

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

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

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

Thanks for great solution Striver

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

The energy man 🙌🔥

Thank You Understood!!!

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

Understood

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; }

Memoization solution is not giving correct answer even though i have made the required chages in it.

ye wala clear nhi hua striver bro! ...isme dikkat aai approach m mujhe ...koi samjha sake to please samjhao mujhe

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

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

why aren't we doing this with the two pointer approach?? we can have total of four pointers... two pointers for the first string and another two pointers for the second string... I tried using this approach and 41 test cases passed out of 50 on code ninjas(code 360)... now I don't know which edge case I am missing...

Understood, Thank you so much.

Understood ❤🔥🔥

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

How are ppl coming with such simple solutions

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

Understood.

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

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

understood …excellent series

Understood!!

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

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

amazing teacher.

Understood!

Consistency 🔥

Understood. Thankyou Sir

Understood

cool man

understood.

UNDERSTOOD💯💯💯

Understood 🙂🙂💚🙏

understood

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]

understood bhayiya as always thank u for all

Understood sir!

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

how will we solve this using recursion, memoization?

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

understood striver

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

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

Give the recursive solution to this..

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

Very good explanation. Thank you so much.

lovely explanation, thanks!

Can someone please help me in printing the substring.For some reason I am getting the wrong answer while printing the string. Thank you.

Amazing observation!

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

Understood, sir. Thank you very much.

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

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

has anyone done by memoization (top down)?

understood sir

code for printing longest common substring #include using namespace std; void lcs(string str1, string str2) { int n =str1.size(); int m= str1.size(); vectordp(n+1, vector(m+1,0)); int row=0; int col =0; int maxi = 0; for(int i=1; i

US striver

Great video bhaiya

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

Understood Thanks 😀

can we further optimize in 1 d araay?

UNDERSTOOD

Understood, thanks!

Thanks for the video!

thanks a lot sir for the playlist

understood very well

done with it ! moving to next