Distinct Subsequences - Dynamic Programming - Leetcode 115 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/count-su...
0:00 - Read the problem
1:05 - Drawing Explanation
9:00 - Coding Explanation
leetcode 115
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#twitter #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@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.

[@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

[@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.

[@runzsh]

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

[@aryanyadav3926]

Wonderful! Will definitely watch your dp series.

[@sk_4142]

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.

[@pritampawar6478]

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

[@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; } }

[@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!

[@vinayakgupta1]

Your channel is GOLD !!!!

[@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

[@swastikgorai2332]

simple and clear! thanks !!!

[@mansimishra7089]

Very Nice Explanation ...Thankyou

[@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.

[@anandjaiswal9870]

Clean Explanation

[@shrimpo6416]

Thank you!

[@tomtran6936]

Love it !

[@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

[@hoyinli7462]

in the question, there is 1 constraint: 1

[@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

[@shrimpo6416]

so clear!

[@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!

[@hoyinli7462]

you made the world super simple again

[@thyminegaming6943]

in if case why can't we write if(s[i]==t[j]){ dp[i][j]= rec(i+1,j+1,s,t,dp)+rec(i+2,j+1,s,t,dp); } instead of if(s[i]==t[j]){ dp[i][j]= rec(i+1,j+1,s,t,dp)+rec(i+1,j,s,t,dp); } can any body please explain me??

[@hoyinli7462]

and liked this video as always. big THX

[@kuangyimeng8850]

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

[@SachinKumar-cd1sg]

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

[@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

[@theWrongCode]

Perfect

[@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.

[@pranjityadav3620]

awesome

[@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.

[@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.

[@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

[@conormurphy5794]

First hard problem i solved

[@nagarjunvinukonda162]

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

[@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.

[@heroicrhythms8302]

Neetcode Nagaraj

[@jonaskhanwald566]

combination sum ???

[@NeetCode]

Combination Sum IV? I can try to do it soon

[@jonaskhanwald566]

@@NeetCode Thanks

[@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)

[@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!

[@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 :)

[@DavidDLee]

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

[@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]

[@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)]