DP 27. Longest Common Substring | DP on Strings 🔥
Вставка
- Опубліковано 26 сер 2024
- Lecture Notes/C++/Java Codes: takeuforward.o...
Problem Link: bit.ly/3H2M3KS
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/take...
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the MCM Dp, this is the first problem on the pattern Partition DP.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.o...
You can also get in touch with me at my social handles: linktr.ee/take...
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.
I am not getting the mismatch condition only please can you elaborate
ha bhai thank you 😂
right I needed to confirm with someone
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].
@@jayantmishra2266yes bro because in tabulation we cannot write the negative condition so we have shifted i-1 to i
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.
Recursion solution
static int lcs(int m, int n, String s1, String s2, int count) {
if(m
Dev manus 🙏
By memorization it takes cubic time complexity
You should have told the recursive approach too. You had done that in all the previous videos.
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)));
}
@@vikasbelida3218 can you share memoization one also ,I'm not able to do it
@@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.
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.
@@datahacker1405 is it even possible to solve this using memoization? I tried but couldn't
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...🙂🙂😍😍
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);
}
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
mr geller i thought you were a paleontologist
@@riteshmohan3454 yeah i also thought he's a polontologist
memoization is not work on this
@@ravindrayadav6103 not working on these TC
1)yxyy
yxy
ans->3
2)yxxzzxxxx
yzyzxxyxxz
ans->4
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!
this question like one of the easiest question after following your videos....thanku striver
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
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
nice brother this is working
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)
Same bro 🤜
from where have you learned dsa ?? if you have not understood a specific topic how to handle it??
search is the only solution go n search
Just in case if anyone needs recursive approach for this:
Recursive code:
def lcs(s, t) :
def solve(i1,i2):
if(i1
best
@@ScrollWthMahadev can convert to c++??
Hey, I am not able to understand why you have done nomatch = min(solve(), solve(), 0) since it would always give 0 for nomatch
same question@@sharmaanuj334
UNDERSTOOD.........Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
for those who want to solve this question on leetcode, it is lc 718
thanks!
understood!..Thanks for explaining this in an elegant way!
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.
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.
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
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.
Why will it not work?
@@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"
@@lokeshdohare2579 i am facing the same problem, did u come up with any modification over striver's code
@@omkumarsingh4194 I came up with a solution, but that's not a dp solution.
@@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
Equivalent leetcode question for this is "718. Maximum Length of Repeated Subarray "
Thanks !
Thanks man. Appreciated.
Thanks bro...👍🏻
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)));
}
here is the recursive & memoization approach..........
// recursive
int func(int ind1,int ind2,string &s1,string &s2,int &ans){
if(ind1
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 🙂
@@anshumaan1024 you are correct bro, return dp[ind1][ind2]=match ;
now,it will be working fine ,thanks
@@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
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;
}
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;
}
}
How its working ?
what is the intuition ..
@@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..
Understood ❤
Understood !!
Thank You, for your hard work..
UNDERSTOOOD UNDERSTOOOD UNDERSTOOOD!!!
BEST TEACHERRRR EVERRRRR!!!!!!!!💯💯💯💯
UNDERSTOOD...!!
Thank you striver for the video... :)
Done and dusted in the revision session :)
Nov'14, 2023 04:37 pm
Thank You
Understood!!!
How are ppl coming with such simple solutions
understood
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
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);
// memoization in C++
class Solution {
vector dp;
public:
int rec(int i,int j,vector& nums1, vector& nums2,int &ans){
if(i
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);
}
what about memoization ?
Understood.
Thanks for great solution Striver
I got the intuition within 4mins of you video.😎😎
Understood
understood :)❤ still we can optimise this to one array by a loop m to 1
so here dp[i][j] indicates that longest common substring in which s1[i] and s2[j] are matching?
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
Understood!
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
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;
}
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
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
Understood, Thank you so much.
Memoization Code for this:
int lcsHelper(string &str1, string &str2, int i, int j, int count, vector& dp) {
if(i == -1 || j == -1) return count;
if(dp[i][j][count] != -1) return dp[i][j][count];
int currentCount = count;
if (str1[i] == str2[j]) {
currentCount = lcsHelper(str1, str2, i-1, j-1, currentCount+1, dp);
}
currentCount = max({currentCount, lcsHelper(str1, str2, i-1, j, 0, dp), lcsHelper(str1, str2, i, j-1, 0, dp)});
return dp[i][j][count] = currentCount;
}
int lcs(string &str1, string &str2){
int n = str1.length();
int m = str2.length();
vector dp(n, vector(m, vector(max(n, m), -1)));
return lcsHelper(str1, str2, n-1, m-1, 0, dp);
}
We need 3-D vector as striver said :)
Recursive Code:
int lcsHelper(string &str1, string &str2, int i, int j, int count) {
if(i == -1 || j == -1) return count;
if (str1[i] == str2[j]) {
count = lcsHelper(str1, str2, i-1, j-1, count+1);
}
count = max({count, lcsHelper(str1, str2, i-1, j, 0), lcsHelper(str1, str2, i, j-1, 0)});
return count;
}
int lcs(string &str1, string &str2){
return lcsHelper(str1, str2, str1.length()-1, str2.length()-1, 0);
}
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 .
---
Dp[1][2] means a from str1 and b from str2. So a and b is not substring so O
The energy man 🙌🔥
understood bhayiya
as always thank u for all
Memoization solution is not giving correct answer even though i have made the required chages in it.
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 teacher.
Understood. Thankyou Sir
Can also be done in O(1) space if we just traverse along the diagonals and keep max consecutive match count
Nah nah, you need the previous values as well.. as in case its not matching. You need to know max!
@@takeUforward
int ans=0;
// diagonals starting from first row
for(int i=0;i
how will we solve this using recursion, memoization?
Understood!!
understood …excellent series
has anyone done by memoization (top down)?
u cannot u need to carry an extra variable!
@@takeUforward it will be complex but we can do it by third variable right?
Suppose the interviewer asked me this particular question
, then firstfall i will explain him the subsequence code and what does the table denotes and then this logic. right??
If i will directly jump into this particular logic then he/she will think i memoize the solution!
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...
Hey Striver, i m getting wrong ans in java code in space optimization, same happened with lcs space optimization
US striver
I think this can not be solved by memoization ie: top-down won't work here ??
please reply
I have searched the whole comment section, i couldn't find any memoized code which has passed all test cases
ig you are right
In space optimization why do we take the length of prev and curr as length of str2.length()+1 why not str1.length()+1.
understood striver
Understood Bhaiya!!
Edit after 4 months - "UNDERSTOOD BHAIYA!!"
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"
Understood sir!
Very good explanation. Thank you so much.
ye wala clear nhi hua striver bro! ...isme dikkat aai approach m mujhe ...koi samjha sake to please samjhao mujhe
Consistency 🔥
Amazing observation!
can we further optimize in 1 d araay?
lovely explanation, thanks!
Understood, sir. Thank you very much.
understood sir
Thanks for the video!
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
Understood, thanks!
Understood 🙂🙂💚🙏
cool man
UNDERSTOOD💯💯💯
Understood Thanks 😀
understand
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
Give the recursive solution to this..
class Solution{
public:
int f(int i, int j, string &s1, string &s2, int &ans){
if( i
thanks a lot sir for the playlist
How to print the longest common substring ?
this is the simplest code
int longestCommonSubstr (string S1, string S2, int n, int m)
{
vector dp(n+1, vector(m+1, 0));
int maxi=0;
for(int i=1; i
Understood bro but the memoization and recursion is quite tough in recursion there is 3d have made😅
bhaiya recursive solution nahi hai kya iska?
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
Thanks bro. It helped
For striver code as well we are getting lcs as 5 bro
done with it ! moving to next