DP 32. Distinct Subsequences | 1D Array Optimisation Technique 🔥

a

In this video, we solve the distinct subsequences problems, which is a pattern in DP on Strings. Here we learn how to match strings.

[RupamSasmalYt]

I couldn't just believe that I've done this problem upto 1d array optimization by It's all for the previous lectures... Striver ! ❤❤🙏🙏

[kartiksuman]

Understood!!! When the space optimization was over, i was like chalo ab ho gya....but when u started converting the at 2 array solution into 1, i was like, "kya chaahiye ab apko????, aur kitna optimize karna h???" codestudio to memorization se hi khush h gya, fir v tabulation kiye, space optimization kiye, now one more gets added to the stack, and that is 1d array optimization., bhaiya kaha se seekhe ap itna sab kuch???...but humours apart...u really put in a lot lot lot of effort in making these videos, can never repay you back for your efforts...only one thing anybody can say, a nd that is THANKYOU.

[DeveshKumar-cypc]

this is the best explation ever. DP seems lot more easier than before. Thank You Striver !!

[visase]

Thanks for making the muscle memory so strong Striver.
This can also be done as below (match+notMatch) rule:
dpMap={}
def recurSubs(index1, index2):
if index2<0:
return 1
if index1<0:
return 0
if (index1, index2) in dpMap:
return dpMap[(index1, index2)]
match=0
if s1[index1]==s2[index2]:
match=recurSubs(index1-1, index2-1)
notMatch=recurSubs(index1-1, index2)
dpMap[(index1, index2)]=match+notMatch
return dpMap[(index1, index2)]

[nikitagupta]

Memoization code will not give TLE if both the strings are passed by reference in the function....
Btw best dp series ever on youtube...Thanks a lot for such a wonderful series !!

[vinayakgandhi]

Best explanation as always, for those who are trying with recursion and memoization, just want to suggest little optimization, that is in the base case add a condition to check if the remaining length of first string is equal to or greater than the remaining length of the second string, if not then simply return a 0 from there no need for further recursive calls from there, so by simply adding the condition if( i < j ) return 0; to memorization code, the recursive (top - down) code works as fast as the tabulation one.

[ishan]

Man you have simplified the optimization of space complexity for me. I was able to optimize it till a single array on my own. I used to struggle with space optimization before. Thank you so much :)

[himanshuparihar]

After watching the problem statement I just pause the video at 7:13 and code all methods by myself:)...all thanks to you bhaiya:)

[rohitkulkarni]

The memoization solution won't give a TLE if we add one more edge case:
if(i<j) return 0;
This will not call further if the string 1 is smaller than string 2

[AquaRegia-iu]

💡Quick Tip : Order of base cases matter. If you first check for i<0 and return 0, it will give wrong answer. This is because suppose i becomes less than 0, but j also becomes less than 0, then you found a subsequence, so it should return 1.
So we need to first check for j<0 and then i<0

[eshaanmandal]

There is a slight problem in the distinct subsequence code if you swap the order of base cases, the code doesn't work

so to get past it one can write

if(i < 0 && j >= 0) return 0;
if(j < 0) return 1;

by doing this you can write your base cases in any order and it wont break

[shubh]

Pure Concepts, clear knowledge, great explanation skills. That's Striver for us!!!

[param_i_am]

Thanks a lot striver! With your amazing explanations and teaching skills, I was able to do this entire problem by myself, i.e Optimization.

FYI: In Tabulation you could also return '% 1e9' . It would still get accepted!

[umangkumar]

this is the best teacher i had seen 1st video of lcs and solve rest by myself

[btRohit-stjp]

Reason why int overflow in tabulation not in memorization, in memorization it will not check all n*m possibility but in tabulation it will check all n*m possibility so in between there is chance in value of dp[i][j] > INT_MAX, try to print dp for with “aazaaa” you will find at dp[i][j] can be greater than dp[n][m]. It is given that dp[n][m] will be lesser than INT_MAX but there is a chance of any dp[i][j] may be greater than INT_MAX, so we need to mark dp of double or unsigned or long long unsigned.

[paritalasuryateja]

A big salute to your hard work for making up dp problems easier striver!!!

[sarankumaar]

I don't know how I did this I solved this problem with in 5mins after reading the question then thinking is this question is even hard. striver I have no words to tell my happiness thank you so much

[namanchandak]

in the memoisation if you write (string &s, string &t) in the recursive function
it will run successful

[AnshuKumar-znqb]

Striver u r amazing This dp playlist is one of the best lecture I have ever found...Thank you for providing such playlist.

[shivangkhanna]

such a great series it prepared me so well that I was able to do this on my own al so upgraded the base case to be l1<l2 return 0