DP 27. Longest Common Substring | DP on Strings 🔥

a

In this video, we solve the MCM Dp, this is the first problem on the pattern Partition DP.

[gandhijainamgunvantkumar]

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.

[PIYUSHRAJ-tv]

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.

[chandanbera]

Recursion solution

static int lcs(int m, int n, String s1, String s2, int count) {
if(m<0 || n <0)
return count;

count = lcs(m-1, n-1, s1, s2, count+1);

count= Math.max(count, Math.max(lcs(m-1, n, s1, s2, 0), lcs(m, n-1, s1, s2, 0)));
return count;
}

[himanshuagrawal]

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

[shaileshsingh]

We can space optimize it to 1D array:-
int findLength(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(), m = nums2.size();
int maxLength = 0;

vector<int> prev(m+1, 0);
for(int i=1; i<=n; i++) {
for(int j=m; j>0; 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;
}

[divyendragahlot]

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

[munnakrish]

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

[sanginigupta]

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!

[raghavmanish]

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

[rossgeller]

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

[sonalidutta]

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<s1.length()-1 && m<s2.length()-1 && s1[n+1] == s2[m+1] ) return dp[n][m] = take;




int lcs(int n, int m, string &s1, string &s2, vector<vector<int>>& dp){
if(n<0 || m<0) return 0;

if(dp[n][m] != -1) return dp[n][m];
int take = 0;

if(s1[n] == s2[m]){
take = 1 ;
if(n > 0 && m > 0 && s1[n-1]==s2[m-1]) take += lcs(n-1, m-1, s1, s2, dp);
}
int notTake = max(lcs(n-1, m, s1, s2, dp), lcs(n, m-1, s1, s2, dp));

if(n<s1.length()-1 && m<s2.length()-1 && s1[n+1] == s2[m+1] ) return dp[n][m] = take;
return dp[n][m] = max(take, notTake);
}

int longestCommonSubstr(string s1, string s2) {
int n = s1.length(), m = s2.length();

vector<vector<int>> dp(n, vector<int>(m, -1));

return lcs(n-1, m-1, s1, s2, dp);;
}

[thanushreddy]

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

[ranasauravsingh]

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

[parthib_deb]

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

[ShubhamVerma-hwuj]

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

[harshitsen]

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.

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

[vikasbelida]

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

[aruna]

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

[vinaykumar]

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