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.
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
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, 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
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.
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))); }
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
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..
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]
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
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
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 . ---
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...
@@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
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
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;
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!
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.
This guy really deserves a medal.
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
#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;
}
UNDERSTOOD.........Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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!..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
Can you share a memoization solution ?
understood striver,may god bless you
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
Understood !!
Thank You, for your hard work..
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
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
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.
Understood ❤
UNDERSTOOOD UNDERSTOOOD UNDERSTOOOD!!!
BEST TEACHERRRR EVERRRRR!!!!!!!!💯💯💯💯
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
Thanks for great solution Striver
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.
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);
Understood, Thank you so much.
for those who want to solve this question on leetcode, it is lc 718
thanks!
Done and dusted in the revision session :)
Nov'14, 2023 04:37 pm
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)));
}
I got the intuition within 4mins of you video.😎😎
UNDERSTOOD...!!
Thank you striver for the video... :)
amazing teacher.
Understood. Thankyou Sir
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 :)❤ still we can optimise this to one array by a loop m to 1
Equivalent leetcode question for this is "718. Maximum Length of Repeated Subarray "
Thanks !
Thanks man. Appreciated.
Thanks bro...👍🏻
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
The energy man 🙌🔥
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..
In space optimization why do we take the length of prev and curr as length of str2.length()+1 why not str1.length()+1.
so here dp[i][j] indicates that longest common substring in which s1[i] and s2[j] are matching?
understood striver
can we further optimize in 1 d araay?
How are ppl coming with such simple solutions
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]
how will we solve this using recursion, memoization?
understood …excellent series
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
understood bhayiya
as always thank u for all
Which board ?? Approach explanation k liye Jo board ya application use ki h konsi h ?
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 sir
Understood sir !
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
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
Understood.
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
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.
brute force will take same time na ?
bhaiya recursive solution nahi hai kya iska?
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 bro but the memoization and recursion is quite tough in recursion there is 3d have made😅
Amazing observation!
Very good explanation. Thank you so much.
Understood Thanks 😀
How to print the longest common substring ?
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 ?
I used to think, this is a. good hard problem, but turns out this is just a 1000 rated problem on CF
US striver
Understood ❤🔥🔥
Understood!
thanks a lot sir for the playlist
Memoization solution is not giving correct answer even though i have made the required chages in it.
Understood, thanks!
Hey Striver, i m getting wrong ans in java code in space optimization, same happened with lcs space optimization
done with it ! moving to next
but how to print this longest common substring
understood very well
Thanks for the video!
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...
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
thanks man
Can someone please help me in printing the substring.For some reason I am getting the wrong answer while printing the string. Thank you.
lovely explanation, thanks!
UNDERSTOOD
UNDERSTOOD💯💯💯
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 Bhaiya!!
Edit after 4 months - "UNDERSTOOD 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, sir. Thank you very much.
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
Understood !!
Great video bhaiya
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!
Understood
#UNDERSTOOD!