Distinct Subsequences - Dynamic Programming - Leetcode 115 - Python

[@NeetCode]

💡 DP PLAYLIST: kzbin.info/www/bejne/bWTVZH6Nnqqpr80

[@dollyvishwakarma2]

Hey @NeetCode, where all do you prefer using a hasmap to a 2D array?

[@nikhil6842]

Watching this at 1 am. I’m more addicted to you playlist than Netflix.

[@ARTEMvorkhlik]

I'm looking forward, one day Netflix will buy the Neetcode's DP playlist and film it.

[@AmeyaGharpure]

There's just something so peaceful about these videos

[@themagickalmagickman]

A really easy optimization that can be added is to check if there are enough characters left in s to create t, this can be done as easily as: if len(s) - i < len(t) - j: return 0. Improves runtime significantly

[@amogh3275]

damn youre right! went from 7% to 98% lol. good catch

[@hetanthakkar5066]

Apart from this trick, How do you come up with such optimization? any specific pointers would help for further problems

[@themagickalmagickman]

@@hetanthakkar5066 I think it just comes down to understanding the code and seeing if there are any obvious deficiencies. When I noticed this optimization, I probably was looking for ways to know when we were done

[@hetanthakkar5066]

@@themagickalmagickman got it.Thank you for the explanation.

[@icvetz]

Just did this problem and also though of this optimization, it increased my runtime from 32ms to 10ms. Glad to see someone else did the same! :)

[@bernardpark3196]

Hey NeetCode, I think there’s a typo on line 14/16 where we’re moving the i pointer forward but not the j pointer - it should be dfs(i + 1, j) instead correct? And thanks again for another great video!

[@NeetCode]

Oh crap... Good catch! You're right, it should be "+ 1" not "+ i", thanks for letting me know!

[@Hiroki-Takahashi]

I was searching the comment section for someone who commented on it :D

[@barked2786]

@@Hiroki-Takahashi me to

[@ermiaazarkhalili5586]

@@Hiroki-Takahashi me too!

[@abilkaiyrdoszhanov7645]

I think this comment is worth pinning:)

[@B0JACK]

Great video, was able to write this after watching! class Solution: def numDistinct(self, s: str, t: str) -> int: @cache def dp( i, j ) -> int: if j == len( t ): return 1 if i == len( s ): return 0 res = dp( i+1, j ) if s[i] == t[j]: res += dp( i+1, j+1 ) return res return dp( 0, 0 )

[@JLJConglomeration]

i can't believe i solved a hard on my own in like 10 minutes, but its all thanks to your 1-D and 2-D DP guides, the patterns start to emerge and this suddenly becomes simple

[@yassineacherkouk]

Men you always save me i almost solved 200 problem in leetcode, and now i start solving DP problems, thank you.

[@sadekjn]

slight optimization: Instead of returning 0 if i == len(s), we can return 0 earlier by checking if len(s) - i < len(t) - j, which means that the rest of s is too small for the rest of t.

[@phaninag7438]

We can add a optimization as first line in the dfs function if (len(t)-j) > (len(s)-i): return 0 As there is no valid matching when length of t to be matched is greater than the characters left in string s

[@karanthacker5554]

big boost in ex. time on leet

[@markolainovic]

Good one!

[@kartikeyrana3736]

i dont usually comment on videos but EXCELLENT video, short, crisp and to the point ! here's the java version class Solution { int[][] cache; public int numDistinct(String s, String t) { if(s.length() == 0) return 0; else if(t.length() == 0) return 1; cache = new int[s.length()+1][t.length()+1]; for(int[] arr : cache) Arrays.fill(arr, -1); return dfs(s, t, 0, 0); } public int dfs(String s, String t, int x, int y){ if(y == t.length()) return 1; else if(x == s.length()) return 0; else if(cache[x][y] != -1) return cache[x][y]; int ans = 0; if(s.charAt(x) == t.charAt(y)) ans += dfs(s,t,x+1,y+1) + dfs(s,t,x+1,y); else ans += dfs(s,t,x+1,y); return cache[x][y] = ans; } }

[@runzsh]

I really like the transition modelling visualization, Thanks for such brilliant explanantion!

[@hoyinli7462]

in the question, there is 1 constraint: 1

[@rishabhsinha3713]

Hey, Thanks for the explanation but I think in the solution it will be `if s[i] == t[j]: cache[(i,j)] = dfs(i+1,j+1) + dfs(i+1,j) else: cache[(i,j)] = dfs(i+1,j)`

[@hwang1607]

That looks correct, not sure why nobody else said this

[@aryanyadav3926]

Wonderful! Will definitely watch your dp series.

[@for_whom_the_bell_tolls]

Maaan, your explanation is brilliant as always

[@vinayakgupta1]

Your channel is GOLD !!!!

[@pritampawar6478]

such a neat and to a point solution keep it up👍👍👍

[@sumeetbisen9708]

It's so simple, really appreciate your work, I wrote a solution for this one but having some trouble with memoization, need some advice: count = 0 def check(sub, i, length): nonlocal count if i>=n: return if length>m: return if sub!=t[:length]: return if sub==t: count+=1 return for j in range(i+1,n): temp = sub sub+=s[j] check(sub, j, length+1) sub = temp for i in range(n): check(s[i], i, 1) return count n and m are lengths of s and t respectively

[@pramodhjajala8021]

Hey Navdeep(@Neetcode), just a small suggestion , May be for the sake of future viewers ,you could fix the typo(i + i) in line 14, may be any kind of overlay on video should do i guess

[@kuangyimeng8850]

Hi, I am confused with the difference between ' dynamic programming ' and ' dfs + cache"

[@SachinKumar-cd1sg]

DFS means recursive solution DFS+memorization==recursion+memoization

[@danielsun716]

1D, DP solution def numDistinct(self, s: str, t: str) -> int: dp = [1] * (len(s) + 1) for j in range(len(t)- 1, -1, -1): nextDP = [0] * (len(s) + 1) for i in range(len(s) - 1, -1, -1): if s[i] == t[j]: nextDP[i] = nextDP[i + 1] + dp[i + 1] else: nextDP[i] = nextDP[i + 1] dp = nextDP return dp[0] And it is pretty efficient.

[@hoyinli7462]

you made the world super simple again

[@aradog3213]

HI! what age did you start programming and how long did it take you to be able to solve most of these questions? im 14 i started 2 months ago and im able to solve most of leetcode's problems but i kinda struggle with dynamic problems thanks!

[@ZQutui]

It's a perfect age, the sooner the better. I would say that your struggling will be solved with practice. Just don't give up and you will succeed in programming

[@aradog3213]

@@ZQutui thanks I sure will!

[@DeGoya]

I've got this solution but I thought it's only a backtrack approach. I assumed there must be another dp solution where we use some kind of table like, for instance, in longest subsequence

[@mansimishra7089]

Very Nice Explanation ...Thankyou

[@TheVideogamemaster9]

Interestingly, when implementing this in JavaScript with a Map, I only get to question 53/65 before the time limit exceeds, even when I use the optimizations listed in the comments.

[@swastikgorai2332]

simple and clear! thanks !!!

[@anandjaiswal9870]

Clean Explanation

[@homyakMilashka]

How do I know when to use like a table dp approach and when to use this recursive with memoization. I really am confused. The recursive is so much easier but it almost always TLEs on leetcode even with memoization.

[@MAK_007]

every single DP problem can be solved using both recursive (top down approach) and tabulation (bottom up approach). its just that some problems are easy to write in recursive form and some are easy to write in tabulation form. but the confusion will stop only when you actually understand why tabulation form works in every single problem. patterns in tabulation form differs more than recursive form hence recursive is easy. but you can learn few patterns in tabulation form thoroughly (best way is debug each step in tabulation form then you will understand easily ) then you can understand most of the problems

[@supinVerse]

class Solution: def numDistinct(self, s: str, t: str) -> int: cache = {} def dfs(i,j): if j==len(t): return 1 if i==len(s): return 0 # if i==len(s) or j==len(t): # return int(j==len(t)) if (i,j) in cache: return cache[(i,j)] if s[i]==t[j]: cache[(i,j)] = dfs(i+1,j+1)+dfs(i+1,j) else: cache[(i,j)] = dfs(i+1,j) return cache[(i,j)] return dfs(0,0)

[@bchen1403]

Can someone explain why we must first examine if j reaches string t's end?

[@yasharthgupta9002]

To take care of the situation when both the i and j ended together since j ended this possible sequence needs to be counted but if you return for the i first it will be 0 hence the formed string will not be counted so we need to check before if j ended and return 1 as required.

[@hoyinli7462]

and liked this video as always. big THX

[@kevinburke3941]

This solution leads to Time Limit Exceeded on Leetcode.

[@anshumansinha5874]

This isn’t dp, right? It’s memoisation (i.e DFS + Hash map)

[@ryanaugustine5940]

DP is an approach to solve recursive problems wherein the overlapping sub-problems are only executed once. So yes when we use memoisation, this is DP.

[@chaitanyasaibeesabathuni928]

There is a huge change when we don't write the base cases in order ; incase we interchange the base case orders we get wrong output!!!!!!!

[@oxyht]

oh shit thanks!

[@shrimpo6416]

Thank you!

[@nagarjunvinukonda162]

Time limit exceeds, you need to do memoization...

[@conormurphy5794]

First hard problem i solved

[@heroicrhythms8302]

Neetcode Nagaraj

[@tomtran6936]

Love it !

[@shrimpo6416]

so clear!

[@juliuskingsley6212]

there is a true DP approach using just O(N) space that beats 85% on LeetCode. class Solution: def numDistinct(self, s: str, t: str) -> int: prevDP = [0] * (len(t) + 1) prevDP[-1] = 1 for i in range(len(s) - 1, -1, -1): currDP = [0] * (len(t) + 1) currDP[-1] = 1 for j in range(len(t) - 1, -1, -1): if s[i] == t[j]: currDP[j] = prevDP[j] + prevDP[j + 1] else: currDP[j] = prevDP[j] prevDP = currDP return prevDP[0]

[@cooldudeakki3435]

Hey NeetCode, I tested this solution for some of the inputs and it didn't output the right answer. Eg: 1. Let s="babgbag" t= "bag"; The output of the program is 2 while the expected output is 5. 2. Let s="rabbbit" t="rabbit"; The output of the program is 1 while the expected output is 3. Kindly look into it.

[@pradipakshar]

Probably because you're checking S[I] == S[J] instead of S[I] == 'T'[J].. 2 years late but hey better late than never :)

[@chaithanyachallapalli8608]

hi can anyone explain this if (s[i] == t[j]) { dp[{i, j}] = dfs(s, t, i + 1, j + 1) + dfs(s, t, i + 1, j); } else { dp[{i, j}] = dfs(s, t, i + 1, j); } insted of this can I do int ans=0; for(int z = i;z

[@jonaskhanwald566]

combination sum ???

[@NeetCode]

Combination Sum IV? I can try to do it soon

[@jonaskhanwald566]

@@NeetCode Thanks

[@kushagrakasliwal3930]

Excellenrtrrtttttt😮

[@theWrongCode]

Perfect

[@DavidDLee]

Why is the complexity M*N? Needs a better explanation.

[@pranjityadav3620]

awesome

[@mohamadilhamramadhan6354]

It could be even O(s) space. Runtime beats 90% and memory beats 90%: dp = [1] * (len(s) + 1) for i in range(len(t)): newRow = [0] for j in range(len(s)): if t[i] == s[j]: newRow.append( newRow[j] + dp[j] ) else: newRow.append( newRow[j]) dp = newRow return dp[len(s)]