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.
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].
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.
#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...🙂🙂😍😍
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!
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'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))); }
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.
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.
@@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"
@@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
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
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
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))); }
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.
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 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..
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
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]
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
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
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 . ---
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
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
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
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; }
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...
Great solution! But why this doesn't work in recursion?? If I write : Int one = 0; if(s1[i - 1] == s2[j - 1]){ one = 1 + func(i - 1 , j - 1 , s1 , s2); } return one;
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.
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;
}
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
i did the same thing but i am getting WA after converting this recursive code to memo code
whyy??
@@hemanthreddysodum-x4w no overlapping sub problems
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...🙂🙂😍😍
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!
UNDERSTOOD.........Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
understood!..Thanks for explaining this in an elegant way!
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
@@SorcererSupreme73 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
this question like one of the easiest question after following your videos....thanku striver
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
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.
Understood !!
Thank You, for your hard work..
understood striver,may god bless you
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
UNDERSTOOOD UNDERSTOOOD UNDERSTOOOD!!!
BEST TEACHERRRR EVERRRRR!!!!!!!!💯💯💯💯
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
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
Understood ❤
Can you share a memoization solution ?
Done and dusted in the revision session :)
Nov'14, 2023 04:37 pm
UNDERSTOOD...!!
Thank you striver for the video... :)
Understood, Thank you so much.
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);
Thanks for great solution Striver
for those who want to solve this question on leetcode, it is lc 718
thanks!
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)));
}
Equivalent leetcode question for this is "718. Maximum Length of Repeated Subarray "
Thanks !
Thanks man. Appreciated.
Thanks bro...👍🏻
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.
thank you US
Understood. Thankyou Sir
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
understood :)❤ still we can optimise this to one array by a loop m to 1
Thank You
Understood!!!
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..
amazing teacher.
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
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
I got the intuition within 4mins of you video.😎😎
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]
Hey Striver, i m getting wrong ans in java code in space optimization, same happened with lcs space optimization
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 sir!
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
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
understood striver
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;
}
Understood!
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 ❤🔥🔥
The energy man 🙌🔥
Understood
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
understood sir
so here dp[i][j] indicates that longest common substring in which s1[i] and s2[j] are matching?
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
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
understood
can we further optimize in 1 d araay?
Which board ?? Approach explanation k liye Jo board ya application use ki h konsi h ?
understood …excellent series
UNDERSTOOD
How are ppl coming with such simple solutions
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);
}
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
Can someone please help me in printing the substring.For some reason I am getting the wrong answer while printing the string. Thank you.
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 🤜
Understood Bhaiya!!
Edit after 4 months - "UNDERSTOOD BHAIYA!!"
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 !!
Understood, thanks!
understood bhayiya
as always thank u for all
I used to think, this is a. good hard problem, but turns out this is just a 1000 rated problem on CF
done with it ! moving to next
// memoization in C++
class Solution {
vector dp;
public:
int rec(int i,int j,vector& nums1, vector& nums2,int &ans){
if(i
Amazing observation!
Understood bro but the memoization and recursion is quite tough in recursion there is 3d have made😅
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
how will we solve this using recursion, memoization?
bhaiya recursive solution nahi hai kya iska?
Understood Thanks 😀
thanks man
Understood!!!!
Very good explanation. Thank you so much.
Thanks for the video!
#UNDERSTOOD!
please add the recursive approch here for lcs
Its complex, and is of higher tc, so not required.
class Solution{
public:
int f(int i, int j, string &s1, string &s2, int &ans){
if( i
Understood!!
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
Consistency 🔥
Hey Striver your given space optimized code for Longest Common Substring gives wrong output for java.
understood
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
US striver
lovely explanation, thanks!
Great solution! But why this doesn't work in recursion?? If I write :
Int one = 0;
if(s1[i - 1] == s2[j - 1]){
one = 1 + func(i - 1 , j - 1 , s1 , s2);
}
return one;
class Solution {
vector dp;
public:
int rec(int i,int j,vector& nums1, vector& nums2,int &ans){
if(i